You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by md...@apache.org on 2012/02/03 19:39:25 UTC
svn commit: r1240286 - in /jackrabbit/sandbox/jackrabbit-microkernel/src:
main/java/org/apache/jackrabbit/ main/java/org/apache/jackrabbit/state/
test/java/org/apache/jackrabbit/state/
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<Operation> operations = new ArrayList<Operation>();
+
+ /**
+ * 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<Operation> 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<Operation> 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<Operation> 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<Operation> 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<Object[]> 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<Operation> operations(final int count) {
+ return new Iterable<Operation>() {
+ int k = count;
+
+ @Override
+ public Iterator<Operation> iterator() {
+ return new Iterator<Operation>() {
+ @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<Path> nodes = new ArrayList<Path>();
+ 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<Path> properties = new ArrayList<Path>();
+ 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<String> nodeNames1 = new HashSet<String>();
+ final Map<String, JsonAtom> properties1 = new HashMap<String, JsonAtom>();
+ collectItems(mk1, path, nodeNames1, properties1);
+
+ final Set<String> nodeNames2 = new HashSet<String>();
+ final Map<String, JsonAtom> properties2 = new HashMap<String, JsonAtom>();
+ 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<String> nodeNames,
+ final Map<String, JsonAtom> 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);
+ }
+}