Author: mduerig Date: Fri Feb 3 18:39:24 2012 New Revision: 1240286 URL: http://svn.apache.org/viewvc?rev=1240286&view=rev Log: Microkernel based prototype of JCR implementation (WIP) - change log consolidation Added: jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/state/ChangeLog.java jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogFuzzTest.java jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogTest.java Modified: jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/Path.java Modified: jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/Path.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/Path.java?rev=1240286&r1=1240285&r2=1240286&view=diff ============================================================================== --- jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/Path.java (original) +++ jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/Path.java Fri Feb 3 18:39:24 2012 @@ -57,7 +57,20 @@ public final class Path { public boolean isRoot() { return "/".equals(jcrPath); } + + public boolean isAncestorOf(Path absPath) { + return workspace.equals(absPath.workspace) && PathUtils.isAncestor(jcrPath, absPath.jcrPath); + } + public Path move(Path from, Path to) { + if (from.isAncestorOf(this)) { + return create(getWorkspace(), to.jcrPath + jcrPath.substring(from.jcrPath.length())); + } + else { + return this; + } + } + public Path concat(String relPath) { if (relPath.isEmpty()) { return this; Added: jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/state/ChangeLog.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/state/ChangeLog.java?rev=1240286&view=auto ============================================================================== --- jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/state/ChangeLog.java (added) +++ jackrabbit/sandbox/jackrabbit-microkernel/src/main/java/org/apache/jackrabbit/state/ChangeLog.java Fri Feb 3 18:39:24 2012 @@ -0,0 +1,584 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.jackrabbit.state; + +import org.apache.jackrabbit.Path; +import org.apache.jackrabbit.json.JsonValue.JsonAtom; + +import java.util.ArrayList; +import java.util.List; + +import static org.apache.jackrabbit.state.ChangeLog.Operation.ID; + +/** + * Instance of this class represent a list of add node, remove node, + * move node, set property and remove property operations. + * The change log is consolidated at any time. That is, a change log + * transforms any valid list of operation into an minimal list of + * operations which is equivalent to the initial list. A list of operation + * is valid, if can be applied to some hierarchy of nodes and properties. + * Two list of operations are equivalent if they have the same effect on + * any hierarchy of node and properties. A list of operations is minimal + * amongst some other list of operations if none of the other lists + * contain more operations. + */ +public class ChangeLog { + private final List operations = new ArrayList(); + + /** + * Add a add node operation to this change log + * @param path path of the added node + */ + public void addNode(Path path) { + addOperation(Operation.addNode(path)); + } + + /** + * Add remove node operation to this change log + * @param path path of the removed node + */ + public void removeNode(Path path) { + addOperation(Operation.removeNode(path)); + } + + /** + * Add a move node operation to this change log + * @param from path of the node to move + * @param to path of the moves node + */ + public void moveNode(Path from, Path to) { + addOperation(Operation.moveNode(from, to)); + } + + /** + * Add a set property operation to this change log + * @param parent parent of the property + * @param name name of the property + * @param value value of the property + */ + public void setProperty(Path parent, String name, JsonAtom value) { + addOperation(Operation.setProperty(parent, name, value)); + } + + /** + * Add a remove property operation to this change log + * @param parent parent of the property + * @param name name of the property + */ + public void removeProperty(Path parent, String name) { + setProperty(parent, name, JsonAtom.NULL); + } + + private void addOperation(Operation operation) { + operations.add(operation); + reduce(operations, operations.size() - 1); + } + + /** + * @return JSOP representation of the consolidated list of operations + */ + public String toJsop() { + StringBuilder sb = new StringBuilder(); + for (Operation op : operations) { + sb.append(op.toJsop()); + } + return sb.toString(); + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + for (Operation op : operations) { + sb.append(op.toString()).append('\n'); + } + return sb.toString(); + } + + //------------------------------------------< private/internal >--- + + /* + The change log consolidation algorithm implemented in the reduce method + is based on algebraic properties of move operations on paths. The other + operations (add node, remove node and set property) are generalized to + move operations. Consolidation relies on reduction and commutation rules + of move operations. + + A move operation resembles a map on a hierarchy (of nodes and properties). + A change log consisting of k move operations m_1 to m_k is thus the composition + of the individual moves: m_1 *, ..., * m_k (using * for function composition: + f(g(x)) = (f * g)(x)). + + Some definitions, notation and propositions: + + * Let NIL denote a path which never occurs in any hierarchy. + + * Order on paths: let p, q be paths. + - p < q iff p != NIL and q != NIL and p is an ancestor of q. + - p <= q iff p < q or p == q != NIL + + * Conflict of paths: let p, q be paths. + - p ~ q (p conflicts with q) iff either p <= q or q <= p + + * Substitution in paths: let p, q, r be paths. + - [p -> q]r = r if p is not an ancestor of r and + - [p -> q]r = s where s is the path resulting from replacing the ancestor + p in r with q otherwise. + + * Let p, q be paths. Then p:q denotes a move operation where the node at + p is moved to a new node at q. + + * Valid moves: leq p, q be paths. + - p:q is valid iff p !~ q or p = q + - if p:q is not valid, it is invalid + + Invalid moves are exactly those which would result in a node being moved + to an ancestor/descendant of itself. + + * Identity on moves: let p, q be paths. + - p:q = ID iff p = q. + + * Conflict on moves: let p, q, r, s be paths. + - p:q ~ r:s (p:q conflicts with r:s) iff either p ~ r or p ~ s or q ~ r + or q ~ s. + + * Strict commutativity of moves: let m, n be moves. + - m * n = n * m iff m !~ n + + * Substitutions in moves: let p, q, r, s be paths. + - [p -> q]r:s = [p -> q]r:[p -> q]s + + * Let p be a path and let +p denote an add node operation and let -p + denote a remove node operation for a node at path p. + - +p = NIL:p That is, adding a node is represented by a move from a + unknown source. + - p = p:NIL. That is, removing a node is represented by a move to an + unknown sink. + + + Let m = p:q, n = r:s with p, q, r, s != NIL be valid moves with m != ID and + n != ID. Then the following reduction and commutation rules apply: + + 1. p!~ r: m * n = n * m + 2. p < r: illegal (since this implies q <= r which implies p ~ q and thus m invalid) + 3. p = r: illegal (since this implies q <= r which implies p ~ q and this m invalid) + 4. p > r: does not commute if q < s. Otherwise m * n = n * [r -> s]m + 5. p!~ s: m * n = n * m + 6. p < s: illegal (since this implies p ~ q and thus m invalid) + 7. p = s: does not commute + 8. p > s: illegal (since p > s implies there is an s already which will conflict with r:s) + 9. q!~ r: m * n = n * m + 10. q < r: m * n = [q -> p]n * m + 11. q = r: m * n = p:s (transitivity of moves) + 12. q > r: m * n = n * [r -> s]m + 13. q!~ s: m * n = n * m + 14. q < s: does not commute if p > r. Otherwise m * n = [q -> p]n * m + 15. q = s: illegal (since s conflicts with r:s) + 16. q > s: illegal (since s conflicts with r:s) + + Allowing add node and remove node operations the following additional conditions apply: + + Let m = p:q, n = r:s be valid moves with m != ID and n != ID. Then the reduction + and commutations rules 1. to 16. apply with extra conditions on 4., 10., 12. and 14.: + + 4'. if s = NIL and q = NIL then m * n = -r. Otherwise if s = NIL then m, n do not commute. + 10'. illegal if p = NIL + 12'. if s = NIL then m * n = -r * -p + 14'. illegal if p = NIL + */ + + /** + * Special path element representing source and sink in add node + * and remove node operations, respectively. NIL is not part of + * the {@code leq}, {@code lt} and {@code conflict} relations below. + */ + private static final Path NIL = Path.create("", "/*"); + + /** + * Partial order on paths: {@code p} <= {@code q} iff {@code p} is an ancestor + * of {@code q} or {@code p} == {@code q} + */ + private static boolean leq(Path p, Path q) { + return p != NIL && q != NIL && (p.equals(q) || p.isAncestorOf(q)); + } + + /** + * Strict partial order on paths: {@code p} < {@code q} iff {@code p} is an + * ancestor of {@code q} + */ + private static boolean lt(Path p, Path q) { + return p != NIL && q != NIL && p.isAncestorOf(q); + } + + /** + * Conflict of paths: {@code p} and {@code q} conflict iff either + * {@code p} <= {@code q} or {@code p} >= {@code q} + */ + private static boolean conflict(Path p, Path q) { + return leq(p, q) || leq(q, p); + } + + /** + * Substitution of ancestor path: replaces {@code from} with {@code to} + * in {@code path} if {@code from} is an ancestor of {@code path} + */ + private static Path subst(Path from, Path to, Path path) { + return path == NIL ? path : path.move(from, to); + } + + /** + * Instances of this class represent operations in the change log. + * The underlying abstraction models operations as a moves: remove + * node is represented as move to {@code NIL} and add node and add + * property are represented as move from {@code NIL}. Add property + * operations carry a value and the property names is disambiguated + * (leading star) in order to avoid conflicts with node names. + */ + static final class Operation { + public static Operation ID = new Operation(NIL, NIL, null); + + private final Path from; + private final Path to; + private final JsonAtom value; + + private Operation(Path from, Path to, JsonAtom value) { + if (from == null || to == null) { + throw new IllegalArgumentException("path is null"); + } + + this.from = from; + this.to = to; + this.value = value; + } + + /** + * Create a new move node operation. + * @param from source of the move + * @param to target of the move + * @return new move node operation or {@code ID} if {@code from} and {@code to} + * are the same path. + * @throws IllegalArgumentException if {@code from} an {@code to} conflict: moving + * a node to its own ancestor/descendant is not possible. + */ + public static Operation moveNode(Path from, Path to) { + if (from.equals(to)) { + return ID; + } + + if (conflict(from, to)) { + // Cannot move node to own ancestor/descendant + throw new IllegalArgumentException("Cannot move " + from + " to " + to); + } + else { + return new Operation(from, to, null); + } + } + + /** + * Create a new add node operation. + * @param path path of the node + * @return new add node operation or {@code ID} if {@code path} is {@code NIL} + */ + public static Operation addNode(Path path) { + return path.equals(NIL) ? ID : new Operation(NIL, path, null); + } + + /** + * Create a new remove node operation. + * @param path path of the node + * @return new remove node operation or {@code ID} if {@code path} is {@code NIL} + */ + public static Operation removeNode(Path path) { + return path.equals(NIL) ? ID : new Operation(path, NIL, null); + } + + /** + * Create a new set property operation. + * @param parent parent of the property + * @param name name of the property + * @param value value of the property + * @return new set property operation + */ + public static Operation setProperty(Path parent, String name, JsonAtom value) { + return new Operation(NIL, encodeProperty(parent, name), value); + } + + /** + * Move this move operation to another ancestor path + * @param source source path + * @param target target path + * @return move operation where {@code target} is substituted for {@code source} + * in both {@code from} and {@code to} of this operation. + */ + public Operation move(Path source, Path target) { + return new Operation(subst(source, target, from), subst(source, target, to), value); + } + + /** + * @return JSOP representation of this operation + */ + public String toJsop() { + if (from == NIL && to == NIL) { + return ""; + } + else if (value != null) { + return "^\"" + decodeProperty(to).toMkPath() + "\":" + value.toJson(); + } + else if (from == NIL) { + return "+\"" + to.toMkPath() + "\":{}"; + } + else if (to == NIL) { + return "-\"" + from.toMkPath() + '"'; + } + else { + return ">\"" + from.toMkPath() + "\":\"" + to.toMkPath() + '"'; + } + } + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + if (!(other instanceof Operation)) { + return false; + } + + Operation that = (Operation) other; + return from.equals(that.from) && to.equals(that.to) + && value == null ? that.value == null : value.equals(that.value); + + } + + @Override + public int hashCode() { + return 31 * (31 * from.hashCode() + to.hashCode()) + (value == null ? 0 : value.hashCode()); + } + + @Override + public String toString() { + if (from == NIL && to == NIL) { + return "ID"; + } + else if (value != null) { + return '^' + decodeProperty(to).toMkPath() + ':' + value.toJson(); + } + else if (from == NIL) { + return '+' + to.toMkPath() + ":{}"; + } + else if (to == NIL) { + return '-' + from.toMkPath(); + } + else { + return '>' + from.toMkPath() + ':' + to.toMkPath(); + } + } + + private static Path encodeProperty(Path parent, String name) { + return parent.concat('*' + name); + } + + private static Path decodeProperty(Path path) { + return path.getParent().concat(path.getName().substring(1)); + } + } + + /** + * Try to commute the two operations at {@code index} and {@code index + 1} in + * the list of operations {@code ops}. Commuting operations might result in + * changes to these operations. The list is modified in place. + * @return {@code true} if commuting was successful, {@code false} otherwise. + */ + private static boolean commute(List ops, int index) { + Operation m = ops.get(index); + Operation n = ops.get(index + 1); + + if (!conflict(m.from, n.from) && !conflict(m.from, n.to) && + !conflict(m.to, n.from) && !conflict(m.to, n.to)) + { + // Strict commutativity. See 1., 5., 9., 13. + ops.set(index, n); + ops.set(index + 1, m); + return true; + } + + if (lt(n.from, m.from)) { // p > r + // See 4'. The case s = NIL and q = NIL is handled in reduceTuple + if (lt(m.to, n.to) || n.to == NIL) { // q < s || s == NIL + return false; + } + else { + ops.set(index, n); + ops.set(index + 1, m.move(n.from, n.to)); + return true; + } + } + else if (m.from != NIL && m.from.equals(n.to)) { // p = s + // See 7. + return false; + } + else if (lt(m.to, n.from)) { // q < r + // See 10'. + if (m.from == NIL) { + throw new IllegalArgumentException(m + ", " + n); + } + + ops.set(index, n.move(m.to, m.from)); + ops.set(index + 1, m); + return true; + } + else if (m.to.equals(n.from)) { // q = r + // See 11. This case is handled in reduceTuple + return false; + } + else if (lt(n.from, m.to)) { // q > r + // See 12'. + if (n.to == NIL) { + ops.set(index, Operation.removeNode(m.from)); + ops.set(index + 1, Operation.removeNode(n.from)); + return true; + } + else { + ops.set(index, n); + ops.set(index + 1, m.move(n.from, n.to)); + return true; + } + } + else if (leq(m.to, n.to)) { // q < s + // See 14'. + if (m.from == NIL) { + return false; + } + else { + ops.set(index, n.move(m.to, m.from)); + ops.set(index + 1, m); + return true; + } + } + else { // See 2., 3., 6., 8., 15. and 16. + throw new IllegalArgumentException(m + ", " + n); + } + } + + /** + * Try to reduce the single operation at {@code index} in the list of + * operations {@code ops}. The list is modified in place, i.e. reduced + * operations are removed. + * @return {@code true} if a reduction occurred, {@code false} otherwise + */ + private static boolean reduceSingleton(List ops, int index) { + if (ops.get(index) == ID) { + ops.remove(index); + return true; + } + else { + return false; + } + } + + /** + * Try to reduce the two operations at {@code index} and {@code index + 1} + * in the list of operations {@code ops} to a single operation. The list is + * modified in place, i.e. reduced operations are removed and replaced with + * the result of the reduction. + * @return index of the operations in {@code ops} which contains the result + * of the reduction or {@code -1} if no reduction occurred. + */ + private static int reduceTuple(List ops, int index) { + Operation m = ops.get(index); + Operation n = ops.get(index + 1); + + if (m == ID) { + // left absorption: ID * x = x + ops.remove(index); + return index; + } + else if (n == ID) { + // right absorption: x * ID = x + ops.remove(index + 1); + return index; + } + else if (m.to != NIL && m.to.equals(n.from)) { + // transitivity: a:b * b:c = a:c (See 11.) + ops.set(index, Operation.moveNode(m.from, n.to)); + ops.remove(index + 1); + return index; + } + else if (m.to == NIL && n.to == NIL && lt(n.from, m.from)) { // p > r + // remove absorption: -a/b * -a = -a (See 4'.) + ops.remove(index); + return index; + } + else if (m.from == NIL && n.to == NIL && lt(n.from, m.to)) { // q > r + // add absorption: +a/b * -a = -a (See 12'.) + ops.remove(index); + return index; + } + else if (m.value != null && n.value != null && m.to.equals(n.to)) { + // set property absorption: ^a:x * ^a:y = ^a:y + ops.remove(index); + return index; + } + else { + return -1; + } + } + + /** + * Reduce a list of operations. Let {@code ops.remove(index)} be + * minimal amongst all its equivalent lists of operations. Then this + * method reduces {@code ops} to a minimal list of operations which + * is equivalent to {@code ops}. + */ + private static boolean reduce(List ops, int index) { + // If the operation at index can be eliminated, we are done + if (reduceSingleton(ops, index)) { + return true; + } + + int reduced = -1; // Index of the operation resulting from reducing two adjacent operations + + // Starting at the new operation, go backward until either a reduction of two + // adjacent operations is found or the two adjacent operations don't commute + int k = index; + do { + if (--k < 0) { + break; + } + reduced = reduceTuple(ops, k); + } while (reduced < 0 && commute(ops, k)); + + // If no reduction found so far... + if (reduced < 0) { + // ...starting at the new operation, go forward until either a reduction of two + // adjacent operations is found or the two adjacent operations don't commute + k = index; + do { + if (++k >= ops.size()) { + break; + } + reduced = reduceTuple(ops, k - 1); + } while (reduced < 0 && commute(ops, k - 1)); + } + + // If a reduction has been found, reduce recursively treating the result + // of the reduction as new operation + return reduced >= 0 && !ops.isEmpty() && reduce(ops, reduced); + } +} Added: jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogFuzzTest.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogFuzzTest.java?rev=1240286&view=auto ============================================================================== --- jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogFuzzTest.java (added) +++ jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogFuzzTest.java Fri Feb 3 18:39:24 2012 @@ -0,0 +1,488 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.jackrabbit.state; + +import org.apache.jackrabbit.Path; +import org.apache.jackrabbit.json.JsonHandler; +import org.apache.jackrabbit.json.JsonParser; +import org.apache.jackrabbit.json.JsonTokenizer; +import org.apache.jackrabbit.json.JsonValue.JsonAtom; +import org.apache.jackrabbit.json.Token; +import org.apache.jackrabbit.json.UnescapingJsonTokenizer; +import org.apache.jackrabbit.mk.MicroKernelFactory; +import org.apache.jackrabbit.mk.api.MicroKernel; +import org.apache.jackrabbit.state.ChangeLogFuzzTest.Operation.AddNode; +import org.apache.jackrabbit.state.ChangeLogFuzzTest.Operation.MoveNode; +import org.apache.jackrabbit.state.ChangeLogFuzzTest.Operation.RemoveNode; +import org.apache.jackrabbit.state.ChangeLogFuzzTest.Operation.Save; +import org.apache.jackrabbit.state.ChangeLogFuzzTest.Operation.SetProperty; +import org.junit.After; +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; +import org.junit.runners.Parameterized.Parameters; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import javax.jcr.ItemExistsException; +import javax.jcr.ItemNotFoundException; +import javax.jcr.RepositoryException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.Set; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +@RunWith(Parameterized.class) +public class ChangeLogFuzzTest { + static final Logger log = LoggerFactory.getLogger(ChangeLogFuzzTest.class); + + private static final Path ROOT = Path.create("root"); + private static final int OP_COUNT = 5000; + + private final Random random; + + private MicroKernel mk1; + private MicroKernel mk2; + private ChangeLogConsolidator changeLogConsolidator; + + @Parameters + public static List seeds() { + return Arrays.asList(new Object[][] { + {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, + {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, + {20}, {21}, {22}, {23}, {24}, {25}, {26}, {27}, {28}, {29}, + {30}, {31}, {32}, {33}, {34}, {35}, {36}, {37}, {38}, {39}, + }); + } + + public ChangeLogFuzzTest(int seed) { + log.info("Seed = {}", seed); + random = new Random(seed); + } + + @Before + public void setup() { + mk1 = MicroKernelFactory.getInstance("fs:target/repository-test/microkernel1;clean"); + mk1.commit("", "+\"/root\":{}", mk1.getHeadRevision(), ""); + + mk2 = MicroKernelFactory.getInstance("fs:target/repository-test/microkernel2;clean"); + mk2.commit("", "+\"/root\":{}", mk2.getHeadRevision(), ""); + + changeLogConsolidator = new ChangeLogConsolidator(mk2); + } + + @After + public void tearDown() { + mk2.dispose(); + mk1.dispose(); + } + + @Test + public void fuzzTest() throws Exception { + for (Operation op : operations(OP_COUNT)) { + log.info("{}", op); + op.apply(mk1); + op.apply(changeLogConsolidator); + if (op instanceof Save) { + checkEqual(ROOT); + } + } + } + + private Iterable operations(final int count) { + return new Iterable() { + int k = count; + + @Override + public Iterator iterator() { + return new Iterator() { + @Override + public boolean hasNext() { + return k-- > 0; + } + + @Override + public Operation next() { + return createOperation(); + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + }; + } + + abstract static class Operation { + abstract void apply(ChangeLogConsolidator changeLogConsolidator) throws RepositoryException; + abstract void apply(MicroKernel mk); + + static class AddNode extends Operation { + private final Path parent; + private final String name; + + AddNode(Path parent, String name) { + this.parent = parent; + this.name = name; + } + + @Override + void apply(ChangeLogConsolidator changeLogConsolidator) throws ItemExistsException { + changeLogConsolidator.addNode(parent, name); + } + + @Override + void apply(MicroKernel mk) { + mk.commit("", "+\"" + parent.concat(name).toMkPath() + "\":{}", + mk.getHeadRevision(), ""); + } + + @Override + public String toString() { + return '+' + parent.concat(name).toMkPath() + ":{}"; + } + } + + static class RemoveNode extends Operation { + private final Path path; + + RemoveNode(Path path) { + this.path = path; + } + + @Override + void apply(ChangeLogConsolidator changeLogConsolidator) throws ItemNotFoundException { + changeLogConsolidator.removeNode(path); + } + + @Override + void apply(MicroKernel mk) { + mk.commit("", "-\"" + path.toMkPath() + '"', mk.getHeadRevision(), ""); + } + + @Override + public String toString() { + return '-' + path.toMkPath(); + } + } + + static class MoveNode extends Operation { + private final Path source; + private final Path destination; + + MoveNode(Path source, Path destParent, String destName) { + this.source = source; + destination = destParent.concat(destName); + } + + @Override + void apply(ChangeLogConsolidator changeLogConsolidator) throws RepositoryException { + changeLogConsolidator.moveNode(source, destination); + } + + @Override + void apply(MicroKernel mk) { + mk.commit("", ">\"" + source.toMkPath() + "\":\"" + destination.toMkPath() + '"', + mk.getHeadRevision(), ""); + } + + @Override + public String toString() { + return '>' + source.toMkPath() + ':' + destination.toMkPath(); + } + } + + static class SetProperty extends Operation { + private final Path parent; + private final String name; + private final JsonAtom value; + + SetProperty(Path parent, String name, JsonAtom value) { + this.parent = parent; + this.name = name; + this.value = value; + } + + @Override + void apply(ChangeLogConsolidator changeLogConsolidator) throws RepositoryException { + changeLogConsolidator.setProperty(parent, name, value); + } + + @Override + void apply(MicroKernel mk) { + mk.commit("", "^\"" + parent.concat(name).toMkPath() + "\":" + value.toJson(), + mk.getHeadRevision(), ""); + } + + @Override + public String toString() { + return '^' + parent.concat(name).toMkPath() + ':' + value.toJson(); + } + } + + static class Save extends Operation { + @Override + void apply(ChangeLogConsolidator changeLogConsolidator) throws RepositoryException { + changeLogConsolidator.save(); + } + + @Override + void apply(MicroKernel mk) { + // empty + } + + @Override + public String toString() { + return "commit"; + } + } + } + + private Operation createOperation() { + Operation op; + do { + switch (random.nextInt(9)) { + case 0: + case 1: + case 2: + op = createAddNode(); + break; + case 3: + op = createRemoveNode(); + break; + case 4: + op = createMoveNode(); + break; + case 5: + op = createAddProperty(); + break; + case 6: + op = createSetProperty(); + break; + case 7: + op = createRemoveProperty(); + break; + case 8: + op = new Save(); + break; + default: + throw new IllegalStateException(); + } + } while (op == null); + return op; + } + + private Operation createAddNode() { + Path parent = chooseNodePath(); + String name = createNodeName(); + return new AddNode(parent, name); + } + + private Operation createRemoveNode() { + Path path = chooseNodePath(); + return ROOT.equals(path) ? null : new RemoveNode(path); + } + + private Operation createMoveNode() { + Path source = chooseNodePath(); + Path destParent = chooseNodePath(); + String destName = createNodeName(); + return ROOT.equals(source) || destParent.toJcrPath().startsWith(source.toJcrPath()) + ? null + : new MoveNode(source, destParent, destName); + } + + private Operation createAddProperty() { + Path parent = chooseNodePath(); + String name = createPropertyName(); + JsonAtom value = createValue(); + return new SetProperty(parent, name, value); + } + + private Operation createSetProperty() { + Path path = choosePropertyPath(); + if (path == null) { + return null; + } + JsonAtom value = createValue(); + return new SetProperty(path.getParent(), path.getName(), value); + } + + private Operation createRemoveProperty() { + Path path = choosePropertyPath(); + if (path == null) { + return null; + } + return new SetProperty(path.getParent(), path.getName(), JsonAtom.NULL); + } + + private int counter; + + private String createNodeName() { + return "N" + counter++; + } + + private String createPropertyName() { + return "P" + counter++; + } + + private Path chooseNodePath() { + Path path = ROOT; + + Path next; + while ((next = chooseNode(path)) != null) { + path = next; + } + + return path; + } + + private Path choosePropertyPath() { + return chooseProperty(chooseNodePath()); + } + + private Path chooseNode(final Path parent) { + final List nodes = new ArrayList(); + String json = mk1.getNodes(parent.toMkPath(), mk1.getHeadRevision(), 0, 0, -1); + new JsonParser(new JsonHandler(){ + @Override + public void object(JsonParser parser, Token key, JsonTokenizer tokenizer) { + new JsonParser(JsonHandler.INSTANCE).parseObject(tokenizer); + nodes.add(parent.concat(key.text())); + } + }).parseObject(new UnescapingJsonTokenizer(json)); + + int k = random.nextInt(nodes.size() + 1); + if (k < nodes.size()) { + return nodes.get(k); + } + else { + return null; + } + } + + private Path chooseProperty(final Path parent) { + final List properties = new ArrayList(); + String json = mk1.getNodes(parent.toMkPath(), mk1.getHeadRevision(), 0, 0, -1); + new JsonParser(new JsonHandler(){ + @Override + public void atom(Token key, Token value) { + if (!key.text().startsWith(":")) { + properties.add(parent.concat(key.text())); + } + } + }).parseObject(new UnescapingJsonTokenizer(json)); + + int k = random.nextInt(properties.size() + 1); + if (k < properties.size()) { + return properties.get(k); + } + else { + return null; + } + } + + private JsonAtom createValue() { + return JsonAtom.string("V" + counter++); + } + + private void checkEqual(Path path) { + assertTrue(path.toString(), mk1.nodeExists(path.toMkPath(), mk1.getHeadRevision())); + assertTrue(path.toString(), mk2.nodeExists(path.toMkPath(), mk2.getHeadRevision())); + + + final Set nodeNames1 = new HashSet(); + final Map properties1 = new HashMap(); + collectItems(mk1, path, nodeNames1, properties1); + + final Set nodeNames2 = new HashSet(); + final Map properties2 = new HashMap(); + collectItems(mk2, path, nodeNames2, properties2); + + assertEquals(path.toString(), nodeNames1, nodeNames2); + assertEquals(path.toString(), properties1, properties2); + + for (String name : nodeNames1) { + checkEqual(path.concat(name)); + } + } + + private static void collectItems(MicroKernel microKernel, Path path, final Set nodeNames, + final Map properties) { + + String json = microKernel.getNodes(path.toMkPath(), microKernel.getHeadRevision(), 0, 0, -1); + new JsonParser(new JsonHandler(){ + @Override + public void object(JsonParser parser, Token key, JsonTokenizer tokenizer) { + new JsonParser(JsonHandler.INSTANCE).parseObject(tokenizer); + nodeNames.add(key.text()); + } + + @Override + public void atom(Token key, Token value) { + super.atom(key, value); + properties.put(key.text(), new JsonAtom(value)); + } + }).parseObject(new UnescapingJsonTokenizer(json)); + } + + private static class ChangeLogConsolidator { + private final MicroKernel microkernel; + private ChangeLog changeLog = new ChangeLog(); + + public ChangeLogConsolidator(MicroKernel microkernel) { + this.microkernel = microkernel; + } + + public void addNode(Path parent, String name) { + changeLog.addNode(parent.concat(name)); + } + + public void removeNode(Path path) { + changeLog.removeNode(path); + } + + public void moveNode(Path source, Path destination) { + changeLog.moveNode(source, destination); + } + + public void setProperty(Path parent, String name, JsonAtom value) { + changeLog.setProperty(parent, name, value); + } + + public void save() { + String jsop = changeLog.toJsop(); + log.info("jsop = {}", jsop); + microkernel.commit("", jsop, microkernel.getHeadRevision(), ""); + changeLog = new ChangeLog(); + } + } +} Added: jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogTest.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogTest.java?rev=1240286&view=auto ============================================================================== --- jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogTest.java (added) +++ jackrabbit/sandbox/jackrabbit-microkernel/src/test/java/org/apache/jackrabbit/state/ChangeLogTest.java Fri Feb 3 18:39:24 2012 @@ -0,0 +1,155 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.jackrabbit.state; + +import org.apache.jackrabbit.Path; +import org.apache.jackrabbit.json.JsonValue.JsonAtom; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +public class ChangeLogTest { + + @Test + public void empty() { + ChangeLog changeLog = new ChangeLog(); + assertTrue(changeLog.toJsop().isEmpty()); + } + + @Test + public void singleton() { + ChangeLog changeLog = new ChangeLog(); + changeLog.addNode(path("/foo")); + assertEquals("+\"//foo\":{}", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + } + + @Test + public void tuples() { + ChangeLog changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.moveNode(path("/c"), path("/d")); + assertEquals(">\"//c\":\"//d\">\"//a\":\"//b\"", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.moveNode(path("/b"), path("/c")); + assertEquals(">\"//a\":\"//c\"", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.moveNode(path("/b"), path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + + changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.moveNode(path("/a"), path("/b")); + assertEquals("+\"//b\":{}", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.removeNode(path("/b")); + assertEquals("-\"//a\"", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.removeNode(path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + } + + @Test + public void triple() { + ChangeLog changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.moveNode(path("/b"), path("/c")); + changeLog.moveNode(path("/c"), path("/d")); + assertEquals(">\"//a\":\"//d\"", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.moveNode(path("/a"), path("/b")); + changeLog.moveNode(path("/x"), path("/y")); + changeLog.moveNode(path("/b"), path("/c")); + assertEquals(">\"//a\":\"//c\">\"//x\":\"//y\"", changeLog.toJsop()); + } + + @Test + public void remove() { + ChangeLog changeLog = new ChangeLog(); + changeLog.removeNode(path("/a/b")); + changeLog.removeNode(path("/a")); + assertEquals("-\"//a\"", changeLog.toJsop()); + } + + @Test + public void removeAdded() { + ChangeLog changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.addNode(path("/a/b")); + changeLog.removeNode(path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + + changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.addNode(path("/a/b")); + changeLog.addNode(path("/a/c")); + changeLog.removeNode(path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + } + + @Test + public void properties() { + ChangeLog changeLog = new ChangeLog(); + changeLog.setProperty(path("/"), "a", JsonAtom.number(42)); + assertEquals("^\"//a\":42", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.setProperty(path("/"), "a", JsonAtom.number(42)); + changeLog.setProperty(path("/"), "a", JsonAtom.number(43)); + assertEquals("^\"//a\":43", changeLog.toJsop()); + + changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.setProperty(path("/a"), "a", JsonAtom.number(42)); + changeLog.removeNode(path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + + changeLog = new ChangeLog(); + changeLog.addNode(path("/a")); + changeLog.setProperty(path("/a"), "a", JsonAtom.number(42)); + changeLog.setProperty(path("/a"), "b", JsonAtom.number(42)); + changeLog.removeNode(path("/a")); + assertTrue(changeLog.toJsop().isEmpty()); + + changeLog = new ChangeLog(); + changeLog.setProperty(path("/"), "a", JsonAtom.number(42)); + changeLog.removeProperty(path("/"), "a"); + assertEquals("^\"//a\":null", changeLog.toJsop()); + } + + //------------------------------------------< private >--- + + private static Path path(String path) { + return Path.create("", path); + } +}