jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mdue...@apache.org
Subject 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/
Date Fri, 03 Feb 2012 18:39:25 GMT
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);
+    }
+}



Mime
View raw message