| /* |
| * 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.oak.spi.security.privilege; |
| |
| import java.util.Arrays; |
| import java.util.HashMap; |
| import java.util.Map; |
| import com.google.common.primitives.Longs; |
| import org.apache.jackrabbit.oak.api.PropertyState; |
| import org.apache.jackrabbit.oak.api.Tree; |
| import org.apache.jackrabbit.oak.api.Type; |
| import org.apache.jackrabbit.oak.plugins.memory.PropertyStates; |
| import org.apache.jackrabbit.oak.spi.security.authorization.permission.Permissions; |
| import org.jetbrains.annotations.NotNull; |
| import org.jetbrains.annotations.Nullable; |
| |
| import static com.google.common.base.Preconditions.checkArgument; |
| |
| /** |
| * Internal representation of JCR privileges. |
| */ |
| public final class PrivilegeBits implements PrivilegeConstants { |
| |
| private static final long NO_PRIVILEGE = 0; |
| private static final long READ_NODES = 1; |
| private static final long READ_PROPERTIES = READ_NODES << 1; |
| private static final long ADD_PROPERTIES = READ_PROPERTIES << 1; |
| private static final long ALTER_PROPERTIES = ADD_PROPERTIES << 1; |
| private static final long REMOVE_PROPERTIES = ALTER_PROPERTIES << 1; |
| private static final long ADD_CHILD_NODES = REMOVE_PROPERTIES << 1; |
| private static final long REMOVE_CHILD_NODES = ADD_CHILD_NODES << 1; |
| private static final long REMOVE_NODE = REMOVE_CHILD_NODES << 1; |
| private static final long READ_AC = REMOVE_NODE << 1; |
| private static final long MODIFY_AC = READ_AC << 1; |
| private static final long NODE_TYPE_MNGMT = MODIFY_AC << 1; |
| private static final long VERSION_MNGMT = NODE_TYPE_MNGMT << 1; |
| private static final long LOCK_MNGMT = VERSION_MNGMT << 1; |
| private static final long LIFECYCLE_MNGMT = LOCK_MNGMT << 1; |
| private static final long RETENTION_MNGMT = LIFECYCLE_MNGMT << 1; |
| private static final long WORKSPACE_MNGMT = RETENTION_MNGMT << 1; |
| private static final long NODE_TYPE_DEF_MNGMT = WORKSPACE_MNGMT << 1; |
| private static final long NAMESPACE_MNGMT = NODE_TYPE_DEF_MNGMT << 1; |
| private static final long PRIVILEGE_MNGMT = NAMESPACE_MNGMT << 1; |
| private static final long USER_MNGMT = PRIVILEGE_MNGMT << 1; |
| private static final long INDEX_DEFINITION_MNGMT = USER_MNGMT << 1; |
| |
| private static final long READ = READ_NODES | READ_PROPERTIES; |
| private static final long MODIFY_PROPERTIES = ADD_PROPERTIES | ALTER_PROPERTIES | REMOVE_PROPERTIES; |
| private static final long WRITE = MODIFY_PROPERTIES | ADD_CHILD_NODES | REMOVE_CHILD_NODES | REMOVE_NODE; |
| private static final long WRITE2 = WRITE | NODE_TYPE_MNGMT; |
| |
| public static final PrivilegeBits EMPTY = new PrivilegeBits(UnmodifiableData.EMPTY); |
| |
| public static final Map<String, PrivilegeBits> BUILT_IN = new HashMap<String, PrivilegeBits>(); |
| static { |
| BUILT_IN.put(REP_READ_NODES, getInstance(READ_NODES)); |
| BUILT_IN.put(REP_READ_PROPERTIES, getInstance(READ_PROPERTIES)); |
| BUILT_IN.put(REP_ADD_PROPERTIES, getInstance(ADD_PROPERTIES)); |
| BUILT_IN.put(REP_ALTER_PROPERTIES, getInstance(ALTER_PROPERTIES)); |
| BUILT_IN.put(REP_REMOVE_PROPERTIES, getInstance(REMOVE_PROPERTIES)); |
| BUILT_IN.put(JCR_ADD_CHILD_NODES, getInstance(ADD_CHILD_NODES)); |
| BUILT_IN.put(JCR_REMOVE_CHILD_NODES, getInstance(REMOVE_CHILD_NODES)); |
| BUILT_IN.put(JCR_REMOVE_NODE, getInstance(REMOVE_NODE)); |
| BUILT_IN.put(JCR_READ_ACCESS_CONTROL, getInstance(READ_AC)); |
| BUILT_IN.put(JCR_MODIFY_ACCESS_CONTROL, getInstance(MODIFY_AC)); |
| BUILT_IN.put(JCR_NODE_TYPE_MANAGEMENT, getInstance(NODE_TYPE_MNGMT)); |
| BUILT_IN.put(JCR_VERSION_MANAGEMENT, getInstance(VERSION_MNGMT)); |
| BUILT_IN.put(JCR_LOCK_MANAGEMENT, getInstance(LOCK_MNGMT)); |
| BUILT_IN.put(JCR_LIFECYCLE_MANAGEMENT, getInstance(LIFECYCLE_MNGMT)); |
| BUILT_IN.put(JCR_RETENTION_MANAGEMENT, getInstance(RETENTION_MNGMT)); |
| BUILT_IN.put(JCR_WORKSPACE_MANAGEMENT, getInstance(WORKSPACE_MNGMT)); |
| BUILT_IN.put(JCR_NODE_TYPE_DEFINITION_MANAGEMENT, getInstance(NODE_TYPE_DEF_MNGMT)); |
| BUILT_IN.put(JCR_NAMESPACE_MANAGEMENT, getInstance(NAMESPACE_MNGMT)); |
| BUILT_IN.put(REP_PRIVILEGE_MANAGEMENT, getInstance(PRIVILEGE_MNGMT)); |
| BUILT_IN.put(REP_USER_MANAGEMENT, getInstance(USER_MNGMT)); |
| BUILT_IN.put(REP_INDEX_DEFINITION_MANAGEMENT, getInstance(INDEX_DEFINITION_MNGMT)); |
| |
| BUILT_IN.put(JCR_READ, PrivilegeBits.getInstance(READ)); |
| BUILT_IN.put(JCR_MODIFY_PROPERTIES, PrivilegeBits.getInstance(MODIFY_PROPERTIES)); |
| BUILT_IN.put(JCR_WRITE, PrivilegeBits.getInstance(WRITE)); |
| BUILT_IN.put(REP_WRITE, PrivilegeBits.getInstance(WRITE2)); |
| } |
| |
| public static final PrivilegeBits NEXT_AFTER_BUILT_INS = getInstance(INDEX_DEFINITION_MNGMT).nextBits(); |
| |
| private final Data d; |
| |
| /** |
| * Private constructor. |
| * |
| * @param d The data that backs this instance. |
| */ |
| private PrivilegeBits(Data d) { |
| this.d = d; |
| } |
| |
| /** |
| * Creates a mutable instance of privilege bits. |
| * |
| * @return a new instance of privilege bits. |
| */ |
| public static PrivilegeBits getInstance() { |
| return new PrivilegeBits(new ModifiableData()); |
| } |
| |
| /** |
| * Creates a mutable instance of privilege bits. |
| * |
| * @param base The base for this mutable instance. |
| * @return a new instance of privilege bits. |
| */ |
| @NotNull |
| public static PrivilegeBits getInstance(@NotNull PrivilegeBits... base) { |
| PrivilegeBits bts = getInstance(); |
| for (PrivilegeBits baseBits : base) { |
| bts.add(baseBits); |
| } |
| return bts; |
| } |
| |
| /** |
| * Get or create an instance of privilege bits for a specific property that |
| * stores privileges. |
| * |
| * @param property The property state storing privilege bits information. |
| * @return an instance of {@code PrivilegeBits} |
| */ |
| @NotNull |
| public static PrivilegeBits getInstance(@Nullable PropertyState property) { |
| if (property == null) { |
| return EMPTY; |
| } |
| |
| int size = property.count(); |
| if (size == 1) { |
| return getInstance(property.getValue(Type.LONG, 0)); |
| } else { |
| long[] longs = new long[size]; |
| for (int i = 0; i < longs.length; i++) { |
| longs[i] = property.getValue(Type.LONG, i); |
| } |
| return getInstance(longs); |
| } |
| } |
| |
| /** |
| * Get or create an instance of privilege bits for a privilege definition. |
| * |
| * @param tree A privilege definition tree or the privileges root. |
| * @return an instance of {@code PrivilegeBits} |
| */ |
| @NotNull |
| public static PrivilegeBits getInstance(@Nullable Tree tree) { |
| if (tree == null) { |
| return EMPTY; |
| } |
| String privName = tree.getName(); |
| if (BUILT_IN.containsKey(privName)) { |
| return BUILT_IN.get(privName); |
| } else if (REP_PRIVILEGES.equals(privName)) { |
| return getInstance(tree.getProperty(REP_NEXT)); |
| } else { |
| return getInstance(tree.getProperty(REP_BITS)); |
| } |
| } |
| |
| /** |
| * Internal method to get or create an instance of privilege bits for the |
| * specified long value. |
| * |
| * @param bits A long value. |
| * @return an instance of {@code PrivilegeBits} |
| */ |
| @NotNull |
| private static PrivilegeBits getInstance(long bits) { |
| if (bits == NO_PRIVILEGE) { |
| return EMPTY; |
| } else { |
| checkArgument(bits > NO_PRIVILEGE); |
| return new PrivilegeBits(new UnmodifiableData(bits)); |
| } |
| } |
| |
| /** |
| * Internal method to create a new instance of {@code PrivilegeBits}. |
| * |
| * @param bits A long array. |
| * @return an instance of {@code PrivilegeBits} |
| */ |
| @NotNull |
| private static PrivilegeBits getInstance(long[] bits) { |
| return new PrivilegeBits(new UnmodifiableData(bits)); |
| } |
| |
| /** |
| * Calculate the granted permissions by evaluating the given privileges. Note, |
| * that only built-in privileges can be mapped to permissions. Any other |
| * privileges will be ignored. |
| * |
| * @param bits The set of privileges present at given tree. |
| * @param parentBits The privileges present on the parent tree. These are |
| * required in order to determine permissions that include a modification |
| * of the parent tree (add_child_nodes, remove_child_nodes). |
| * @param isAllow {@code true} if the privileges are granted; {@code false} |
| * otherwise. |
| * @return the resulting permissions. |
| */ |
| public static long calculatePermissions(@NotNull PrivilegeBits bits, |
| @NotNull PrivilegeBits parentBits, |
| boolean isAllow) { |
| long privs = bits.d.longValue(); |
| long parentPrivs = parentBits.d.longValue(); |
| long perm = Permissions.NO_PERMISSION; |
| if ((privs & READ) == READ) { |
| perm |= Permissions.READ; |
| } else { |
| if ((privs & READ_NODES) == READ_NODES) { |
| perm |= Permissions.READ_NODE; |
| } else if (((privs & READ_PROPERTIES) == READ_PROPERTIES)) { |
| perm |= Permissions.READ_PROPERTY; |
| } |
| } |
| if ((privs & MODIFY_PROPERTIES) == MODIFY_PROPERTIES) { |
| perm |= Permissions.SET_PROPERTY; |
| } else { |
| if ((privs & ADD_PROPERTIES) == ADD_PROPERTIES) { |
| perm |= Permissions.ADD_PROPERTY; |
| } |
| if ((privs & ALTER_PROPERTIES) == ALTER_PROPERTIES) { |
| perm |= Permissions.MODIFY_PROPERTY; |
| } |
| if ((privs & REMOVE_PROPERTIES) == REMOVE_PROPERTIES) { |
| perm |= Permissions.REMOVE_PROPERTY; |
| } |
| } |
| |
| // add_node permission is granted through privilege on the parent. |
| if ((parentPrivs & ADD_CHILD_NODES) == ADD_CHILD_NODES) { |
| perm |= Permissions.ADD_NODE; |
| } |
| |
| /* |
| remove_node is |
| allowed: only if remove_child_nodes privilege is present on |
| the parent AND remove_node is present on the node itself |
| denied : if either remove_child_nodes is denied on the parent |
| OR remove_node is denied on the node itself. |
| */ |
| if (isAllow) { |
| if ((parentPrivs & REMOVE_CHILD_NODES) == REMOVE_CHILD_NODES && |
| (privs & REMOVE_NODE) == REMOVE_NODE) { |
| perm |= Permissions.REMOVE_NODE; |
| } |
| } else { |
| if ((parentPrivs & REMOVE_CHILD_NODES) == REMOVE_CHILD_NODES || |
| (privs & REMOVE_NODE) == REMOVE_NODE) { |
| perm |= Permissions.REMOVE_NODE; |
| } |
| } |
| |
| // modify_child_node_collection permission |
| if ((privs & ADD_CHILD_NODES) == ADD_CHILD_NODES && |
| (privs & REMOVE_CHILD_NODES) == REMOVE_CHILD_NODES) { |
| perm |= Permissions.MODIFY_CHILD_NODE_COLLECTION; |
| } |
| |
| // the remaining (special) permissions are simply defined on the node |
| if ((privs & READ_AC) == READ_AC) { |
| perm |= Permissions.READ_ACCESS_CONTROL; |
| } |
| if ((privs & MODIFY_AC) == MODIFY_AC) { |
| perm |= Permissions.MODIFY_ACCESS_CONTROL; |
| } |
| if ((privs & LIFECYCLE_MNGMT) == LIFECYCLE_MNGMT) { |
| perm |= Permissions.LIFECYCLE_MANAGEMENT; |
| } |
| if ((privs & LOCK_MNGMT) == LOCK_MNGMT) { |
| perm |= Permissions.LOCK_MANAGEMENT; |
| } |
| if ((privs & NODE_TYPE_MNGMT) == NODE_TYPE_MNGMT) { |
| perm |= Permissions.NODE_TYPE_MANAGEMENT; |
| } |
| if ((privs & RETENTION_MNGMT) == RETENTION_MNGMT) { |
| perm |= Permissions.RETENTION_MANAGEMENT; |
| } |
| if ((privs & VERSION_MNGMT) == VERSION_MNGMT) { |
| perm |= Permissions.VERSION_MANAGEMENT; |
| } |
| if ((privs & WORKSPACE_MNGMT) == WORKSPACE_MNGMT) { |
| perm |= Permissions.WORKSPACE_MANAGEMENT; |
| } |
| if ((privs & NODE_TYPE_DEF_MNGMT) == NODE_TYPE_DEF_MNGMT) { |
| perm |= Permissions.NODE_TYPE_DEFINITION_MANAGEMENT; |
| } |
| if ((privs & NAMESPACE_MNGMT) == NAMESPACE_MNGMT) { |
| perm |= Permissions.NAMESPACE_MANAGEMENT; |
| } |
| if ((privs & PRIVILEGE_MNGMT) == PRIVILEGE_MNGMT) { |
| perm |= Permissions.PRIVILEGE_MANAGEMENT; |
| } |
| if ((privs & USER_MNGMT) == USER_MNGMT) { |
| perm |= Permissions.USER_MANAGEMENT; |
| } |
| if ((privs & INDEX_DEFINITION_MNGMT) == INDEX_DEFINITION_MNGMT) { |
| perm |= Permissions.INDEX_DEFINITION_MANAGEMENT; |
| } |
| return perm; |
| } |
| |
| /** |
| * Returns {@code true} if this privilege bits includes no privileges |
| * at all. |
| * |
| * @return {@code true} if this privilege bits includes no privileges |
| * at all; {@code false} otherwise. |
| * @see org.apache.jackrabbit.oak.spi.security.authorization.permission.Permissions#NO_PERMISSION |
| */ |
| public boolean isEmpty() { |
| return d.isEmpty(); |
| } |
| |
| /** |
| * Returns an unmodifiable instance. |
| * |
| * @return an unmodifiable {@code PrivilegeBits} instance. |
| */ |
| @NotNull |
| public PrivilegeBits unmodifiable() { |
| if (d instanceof ModifiableData) { |
| if (d.isSimple()) { |
| return getInstance(d.longValue()); |
| } else { |
| long[] bits = d.longValues(); |
| long[] copy = new long[bits.length]; |
| System.arraycopy(bits, 0, copy, 0, bits.length); |
| return getInstance(copy); |
| } |
| } else { |
| return this; |
| } |
| } |
| |
| @NotNull |
| public PrivilegeBits modifiable() { |
| if (d instanceof ModifiableData) { |
| return this; |
| } else { |
| return getInstance(this); |
| } |
| } |
| |
| /** |
| * Returns {@code true} if all privileges defined by the specified |
| * {@code otherBits} are present in this instance. |
| * |
| * @param otherBits |
| * @return {@code true} if all privileges defined by the specified |
| * {@code otherBits} are included in this instance; {@code false} |
| * otherwise. |
| */ |
| public boolean includes(@NotNull PrivilegeBits otherBits) { |
| return d.includes(otherBits.d); |
| } |
| |
| /** |
| * Adds the other privilege bits to this instance. |
| * |
| * @param other The other privilege bits to be added. |
| * @return The updated instance. |
| * @throws UnsupportedOperationException if this instance is immutable. |
| */ |
| @NotNull |
| public PrivilegeBits add(@NotNull PrivilegeBits other) { |
| if (d instanceof ModifiableData) { |
| ((ModifiableData) d).add(other.d); |
| return this; |
| } else { |
| throw unsupported(); |
| } |
| } |
| |
| /** |
| * Subtracts the other PrivilegeBits from the this.<br> |
| * If the specified bits do not intersect with this, it isn't modified.<br> |
| * If {@code this} is included in {@code other} {@link #EMPTY empty} |
| * privilege bits is returned. |
| * |
| * @param other The other privilege bits to be subtracted from this instance. |
| * @return The updated instance. |
| * @throws UnsupportedOperationException if this instance is immutable. |
| */ |
| @NotNull |
| public PrivilegeBits diff(@NotNull PrivilegeBits other) { |
| if (d instanceof ModifiableData) { |
| ((ModifiableData) d).diff(other.d); |
| return this; |
| } else { |
| throw unsupported(); |
| } |
| } |
| |
| /** |
| * Subtracts the {@code b} from {@code a} and adds the result (diff) |
| * to this instance. |
| * |
| * @param a An instance of privilege bits. |
| * @param b An instance of privilege bits. |
| * @return The updated instance. |
| * @throws UnsupportedOperationException if this instance is immutable. |
| */ |
| @NotNull |
| public PrivilegeBits addDifference(@NotNull PrivilegeBits a, @NotNull PrivilegeBits b) { |
| if (d instanceof ModifiableData) { |
| ((ModifiableData) d).addDifference(a.d, b.d); |
| return this; |
| } else { |
| throw unsupported(); |
| } |
| } |
| |
| /** |
| * Retains the elements in this {@code PrivilegeBits} that are contained in |
| * the specified other {@code PrivilegeBits}. |
| * |
| * @param other Other privilege bits. |
| * @return This modifiable instance of privilege bits modified such it contains |
| * only privileges that were also contained in the {@code other} instance. |
| */ |
| @NotNull |
| public PrivilegeBits retain(@NotNull PrivilegeBits other) { |
| if (d instanceof ModifiableData) { |
| ((ModifiableData) d).retain(other.d); |
| return this; |
| } else { |
| throw unsupported(); |
| } |
| } |
| |
| @NotNull |
| public PropertyState asPropertyState(String name) { |
| return PropertyStates.createProperty(name, Longs.asList(d.longValues()), Type.LONGS); |
| } |
| |
| /** |
| * Method to calculate the next privilege bits associated with this instance. |
| * |
| * @return an new instance of {@code PrivilegeBits} |
| */ |
| @NotNull |
| public PrivilegeBits nextBits() { |
| if (this == EMPTY) { |
| return EMPTY; |
| } else { |
| return new PrivilegeBits(d.next()); |
| } |
| } |
| |
| /** |
| * Write this instance as property to the specified tree. |
| * |
| * @param tree The target tree. |
| */ |
| public void writeTo(@NotNull Tree tree) { |
| String name = (REP_PRIVILEGES.equals(tree.getName())) ? REP_NEXT : REP_BITS; |
| tree.setProperty(asPropertyState(name)); |
| } |
| |
| private static UnsupportedOperationException unsupported() { |
| return new UnsupportedOperationException("immutable privilege bits"); |
| } |
| |
| //-------------------------------------------------------------< Object >--- |
| @Override |
| public int hashCode() { |
| return d.hashCode(); |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o == this) { |
| return true; |
| } else if (o instanceof PrivilegeBits) { |
| return d.equals(((PrivilegeBits) o).d); |
| } else { |
| return false; |
| } |
| } |
| |
| @Override |
| public String toString() { |
| StringBuilder sb = new StringBuilder("PrivilegeBits: "); |
| if (d.isSimple()) { |
| sb.append(d.longValue()); |
| } else { |
| sb.append(Arrays.toString(d.longValues())); |
| } |
| return sb.toString(); |
| } |
| |
| //------------------------------------------------------< inner classes >--- |
| |
| /** |
| * Base class for the internal privilege bits representation and handling. |
| */ |
| private abstract static class Data { |
| |
| abstract boolean isEmpty(); |
| |
| abstract long longValue(); |
| |
| abstract long[] longValues(); |
| |
| abstract boolean isSimple(); |
| |
| abstract Data next(); |
| |
| abstract boolean includes(Data other); |
| |
| /** |
| * Checks if all {@code otherBits} is already included in {@code bits}. |
| * <p> |
| * Truth table: |
| * <pre> |
| * | b\o | 0 | 1 | |
| * | 0 | 1 | 0 | |
| * | 1 | 1 | 1 | |
| * </pre> |
| * @param bits the super set of bits |
| * @param otherBits the bits to check against |
| * @return {@code true} if all other bits are included in bits. |
| */ |
| static boolean includes(long bits, long otherBits) { |
| return (bits | ~otherBits) == -1; |
| } |
| |
| /** |
| * Checks if all {@code otherBits} is already included in {@code bits}. |
| * <p> |
| * Truth table: |
| * <pre> |
| * | b\o | 0 | 1 | |
| * | 0 | 1 | 0 | |
| * | 1 | 1 | 1 | |
| * </pre> |
| * @param bits the super set of bits |
| * @param otherBits the bits to check against |
| * @return {@code true} if all other bits are included in bits. |
| */ |
| static boolean includes(long[] bits, long[] otherBits) { |
| if (otherBits.length <= bits.length) { |
| // test for each long if is included |
| for (int i = 0; i < otherBits.length; i++) { |
| if ((bits[i] | ~otherBits[i]) != -1) { |
| return false; |
| } |
| } |
| return true; |
| } else { |
| // otherbits array is longer > cannot be included in bits |
| return false; |
| } |
| } |
| } |
| |
| /** |
| * Immutable Data object |
| */ |
| private static final class UnmodifiableData extends Data { |
| |
| private static final long MAX = Long.MAX_VALUE / 2; |
| private static final UnmodifiableData EMPTY = new UnmodifiableData(NO_PRIVILEGE); |
| |
| private final long bits; |
| private final long[] bitsArr; |
| private final boolean isSimple; |
| |
| private UnmodifiableData(long bits) { |
| this.bits = bits; |
| bitsArr = new long[]{bits}; |
| isSimple = true; |
| } |
| |
| private UnmodifiableData(long[] bitsArr) { |
| bits = NO_PRIVILEGE; |
| this.bitsArr = bitsArr; |
| isSimple = false; |
| } |
| |
| @Override |
| boolean isEmpty() { |
| return this == EMPTY; |
| } |
| |
| @Override |
| long longValue() { |
| return bits; |
| } |
| |
| @Override |
| long[] longValues() { |
| return bitsArr; |
| } |
| |
| @Override |
| boolean isSimple() { |
| return isSimple; |
| } |
| |
| @Override |
| Data next() { |
| if (this == EMPTY) { |
| return EMPTY; |
| } else if (isSimple) { |
| if (bits < MAX) { |
| long b = bits << 1; |
| return new UnmodifiableData(b); |
| } else { |
| return new UnmodifiableData(new long[]{bits}).next(); |
| } |
| } else { |
| long[] bts; |
| long last = bitsArr[bitsArr.length - 1]; |
| if (last < MAX) { |
| bts = new long[bitsArr.length]; |
| System.arraycopy(bitsArr, 0, bts, 0, bitsArr.length); |
| bts[bts.length - 1] = last << 1; |
| } else { |
| bts = new long[bitsArr.length + 1]; |
| bts[bts.length - 1] = 1; |
| } |
| return new UnmodifiableData(bts); |
| } |
| } |
| |
| @Override |
| boolean includes(Data other) { |
| if (isSimple) { |
| return (other.isSimple()) && includes(bits, other.longValue()); |
| } else { |
| return includes(bitsArr, other.longValues()); |
| } |
| } |
| |
| //---------------------------------------------------------< Object >--- |
| @Override |
| public int hashCode() { |
| return (isSimple) ? Long.valueOf(bits).hashCode() : Arrays.hashCode(bitsArr); |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o == this) { |
| return true; |
| } else if (o instanceof UnmodifiableData) { |
| UnmodifiableData d = (UnmodifiableData) o; |
| if (isSimple != d.isSimple) { |
| return false; |
| } |
| if (isSimple) { |
| return bits == d.bits; |
| } else { |
| return Arrays.equals(bitsArr, d.bitsArr); |
| } |
| } else { |
| return false; |
| } |
| } |
| } |
| |
| /** |
| * Mutable implementation of the Data base class. |
| */ |
| private static final class ModifiableData extends Data { |
| |
| private long[] bits; |
| |
| private ModifiableData() { |
| bits = new long[]{NO_PRIVILEGE}; |
| } |
| |
| @Override |
| boolean isEmpty() { |
| return bits.length == 1 && bits[0] == NO_PRIVILEGE; |
| } |
| |
| @Override |
| long longValue() { |
| return (bits.length == 1) ? bits[0] : NO_PRIVILEGE; |
| } |
| |
| @Override |
| long[] longValues() { |
| return bits; |
| } |
| |
| @Override |
| boolean isSimple() { |
| return bits.length == 1; |
| } |
| |
| @Override |
| Data next() { |
| throw new UnsupportedOperationException("Not implemented."); |
| } |
| |
| @Override |
| boolean includes(Data other) { |
| if (bits.length == 1) { |
| return other.isSimple() && includes(bits[0], other.longValue()); |
| } else { |
| return includes(bits, other.longValues()); |
| } |
| } |
| |
| /** |
| * Add the other Data to this instance. |
| * |
| * @param other |
| */ |
| private void add(Data other) { |
| if (other != this) { |
| if (bits.length == 1 && other.isSimple()) { |
| bits[0] |= other.longValue(); |
| } else { |
| or(other.longValues()); |
| } |
| } |
| } |
| |
| /** |
| * Subtract the other Data from this instance. |
| * |
| * @param other |
| */ |
| private void diff(Data other) { |
| if (bits.length == 1 && other.isSimple()) { |
| bits[0] = bits[0] & ~other.longValue(); |
| } else { |
| bits = diff(bits, other.longValues()); |
| } |
| } |
| |
| /** |
| * Add the diff between the specified Data a and b. |
| * |
| * @param a |
| * @param b |
| */ |
| private void addDifference(Data a, Data b) { |
| if (a.isSimple() && b.isSimple()) { |
| bits[0] |= a.longValue() & ~b.longValue(); |
| } else { |
| long[] diff = diff(a.longValues(), b.longValues()); |
| or(diff); |
| } |
| } |
| |
| private void or(long[] b) { |
| if (b.length > bits.length) { |
| // enlarge the array |
| long[] res = new long[b.length]; |
| System.arraycopy(bits, 0, res, 0, bits.length); |
| bits = res; |
| } |
| for (int i = 0; i < b.length; i++) { |
| bits[i] |= b[i]; |
| } |
| } |
| |
| private void retain(Data other) { |
| if (isSimple()) { |
| bits[0] &= other.longValue(); |
| } else { |
| long[] lvs = longValues(); |
| long[] bLvs = other.longValues(); |
| |
| long[] res = (lvs.length <= bLvs.length) ? new long[lvs.length] : new long[bLvs.length]; |
| int compactSize = -1; |
| for (int i = 0; i < res.length; i++) { |
| res[i] = (lvs[i] & bLvs[i]); |
| if (res[i] == 0) { |
| if (compactSize == -1) { |
| compactSize = i+1; |
| } |
| } else { |
| compactSize = -1; |
| } |
| } |
| if (compactSize != -1 && res.length > compactSize) { |
| bits = Arrays.copyOfRange(res, 0, compactSize); |
| } else { |
| bits = res; |
| } |
| } |
| } |
| |
| private static long[] diff(long[] a, long[] b) { |
| int index = -1; |
| long[] res = new long[((a.length > b.length) ? a.length : b.length)]; |
| for (int i = 0; i < res.length; i++) { |
| if (i < a.length && i < b.length) { |
| res[i] = a[i] & ~b[i]; |
| } else { |
| res[i] = (i < a.length) ? a[i] : 0; |
| } |
| // remember start of trailing 0 array entries |
| if (res[i] != 0) { |
| index = -1; |
| } else if (index == -1) { |
| index = i; |
| } |
| } |
| switch (index) { |
| case -1: |
| // no need to remove trailing 0-long from the array |
| return res; |
| case 0: |
| // array consisting of one or multiple 0 |
| return new long[]{NO_PRIVILEGE}; |
| default: |
| // remove trailing 0-long entries from the array |
| long[] r2 = new long[index]; |
| System.arraycopy(res, 0, r2, 0, index); |
| return r2; |
| } |
| } |
| } |
| } |
