```+     * Example:
+     *      Assume a set of created roles forming nodes:
+     *            {a1, a2, a3, b, c, d, e, f, h, j}
+     *
+     *      Assume a set of GRANT statements forming arcs:
+     *
+     *      GRANT a1 TO b;   GRANT b TO e;  GRANT e TO h;
+     *      GRANT a1 TO c;                  GRANT e TO f;
+     *      GRANT a2 TO c;   GRANT c TO f;  GRANT f TO h;
+     *      GRANT a3 TO d;   GRANT d TO f;  GRANT a1 to j;
+     *
+     *
+     *          a1            a2         a3
+     *         / | \           |          |
+     *        /  b  +--------> c          d
+     *       j   |              \        /
+     *           e---+           \      /
+     *            \   \           \    /
+     *             \   \---------+ \  /
+     *              \             \_ f
+     *               \             /
+     *                \           /
+     *                 \         /
+     *                  \       /
+     *                   \     /
+     *                    \   /
+     *                      h
+     * ```
+ * An iterator on the inverse relation starting at h for the above + * grant graph will return: + *
```+     *       closure(h, grant-inv) = {e, b, a1, f, c, a2, d, a3}
+     * ```
+ *

+ * An iterator on normal (not inverse) relation starting at a1 for + * the above grant graph will return: + *

```+     *       closure(a1, grant)    = {b, j, e, h, f, c}
+     * ```
+ * + * @return a role name identifying a yet unseen node, or null if + * the closure is exhausted. The order in which the nodes + * are returned is not defined. + */ + public String next(); + + + /** + * This method should be called after the iteration is completed. + * + * @throws StandardException + */ + public void close() throws StandardException; + + +} Propchange: db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/dictionary/RoleClosureIterator.java ------------------------------------------------------------------------------ svn:eol-style = native Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/dictionary/RoleGrantDescriptor.java URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/dictionary/RoleGrantDescriptor.java?rev=670284&r1=670283&r2=670284&view=diff ============================================================================== --- db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/dictionary/RoleGrantDescriptor.java (original) +++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/dictionary/RoleGrantDescriptor.java Sat Jun 21 18:09:48 2008 @@ -35,9 +35,9 @@ /** * This class is used by rows in the SYS.SYSROLES system table. * - * An instance contains information for exactly: - * One , cf. ISO/IEC 9075-2:2003 section 12.4 *or* - * one , section 12.5. + * An instance contains information for exactly: One <role + * definition>, cf. ISO/IEC 9075-2:2003 section 12.4 + * or one <grant role statement>, section 12.5. * * A role definition is also modeled as a role grant (hence the class * name), but with the special grantor "_SYSTEM", and with a grantee Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/DataDictionaryImpl.java URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/DataDictionaryImpl.java?rev=670284&r1=670283&r2=670284&view=diff ============================================================================== --- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/DataDictionaryImpl.java (original) +++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/DataDictionaryImpl.java Sat Jun 21 18:09:48 2008 @@ -54,6 +54,7 @@ import org.apache.derby.iapi.sql.dictionary.PermissionsDescriptor; import org.apache.derby.iapi.sql.dictionary.ReferencedKeyConstraintDescriptor; import org.apache.derby.iapi.sql.dictionary.RoleGrantDescriptor; +import org.apache.derby.iapi.sql.dictionary.RoleClosureIterator; import org.apache.derby.iapi.sql.dictionary.SPSDescriptor; import org.apache.derby.iapi.sql.dictionary.SchemaDescriptor; import org.apache.derby.iapi.sql.dictionary.CheckConstraintDescriptor; @@ -2968,6 +2969,110 @@ return false; } + /** + * Return an in-memory representation of the role grant graph (sans + * grant of roles to users, only role-role relation. + * + * @param tc Transaction Controller + * @param inverse make graph on inverse grant relation + * @return hash map representing role grant graph. + *
• Key: rolename,
• + *
• Value: List representing a + * grant of that rolename to another role (not user). + *
• + *
+ * + * FIXME: Need to cache graph and invalidate when role graph is modified. + * Currently, we always read from SYSROLES. + */ + private HashMap getRoleGrantGraph(TransactionController tc, boolean inverse) + throws StandardException { + + HashMap hm = new HashMap(); + + TabInfoImpl ti = getNonCoreTI(SYSROLES_CATALOG_NUM); + SYSROLESRowFactory rf = (SYSROLESRowFactory) ti.getCatalogRowFactory(); + + DataValueDescriptor isDefOrderable = new SQLVarchar("N"); + ScanQualifier[][] scanQualifier = exFactory.getScanQualifier(1); + + scanQualifier[0][0].setQualifier( + SYSROLESRowFactory.SYSROLES_ISDEF - 1, /* to zero-based */ + isDefOrderable, + Orderable.ORDER_OP_EQUALS, + false, + false, + false); + + ScanController sc = tc.openScan( + ti.getHeapConglomerate(), + false, // don't hold open across commit + 0, // for update + TransactionController.MODE_RECORD, + TransactionController.ISOLATION_REPEATABLE_READ, + (FormatableBitSet) null, // all fields as objects + (DataValueDescriptor[]) null, // start position - + 0, // startSearchOperation - none + scanQualifier, // + (DataValueDescriptor[]) null, // stop position -through last row + 0); // stopSearchOperation - none + + ExecRow outRow = rf.makeEmptyRow(); + RoleGrantDescriptor grantDescr; + + while (sc.fetchNext(outRow.getRowArray())) { + grantDescr = (RoleGrantDescriptor)rf.buildDescriptor( + outRow, + (TupleDescriptor) null, + this); + + // Next call is potentially inefficient. We could read in + // definitions first in a separate hash table limiting + // this to a 2-pass scan. + RoleGrantDescriptor granteeDef = getRoleDefinitionDescriptor + (grantDescr.getGrantee()); + + if (granteeDef == null) { + // not a role, must be user authid, skip + continue; + } + + String hashKey; + if (inverse) { + hashKey = granteeDef.getRoleName(); + } else { + hashKey = grantDescr.getRoleName(); + } + + List arcs = (List)hm.get(hashKey); + if (arcs == null) { + arcs = new LinkedList(); + } + + arcs.add(grantDescr); + hm.put(hashKey, arcs); + } + + sc.close(); + + return hm; + + } + + /** + * @see DataDictionary#createRoleClosureIterator + */ + public RoleClosureIterator createRoleClosureIterator + (TransactionController tc, + String role, + boolean inverse + ) throws StandardException { + + HashMap graph = getRoleGrantGraph(tc, inverse); + + return new RoleClosureIteratorImpl(role, inverse, graph); + } + /** * Drop all permission descriptors corresponding to a grant to Added: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/RoleClosureIteratorImpl.java URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/RoleClosureIteratorImpl.java?rev=670284&view=auto ============================================================================== --- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/RoleClosureIteratorImpl.java (added) +++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/catalog/RoleClosureIteratorImpl.java Sat Jun 21 18:09:48 2008 @@ -0,0 +1,179 @@ +/* + + Derby - Class org.apache.derby.impl.sql.catalog.RoleClosureIteratorImpl + + 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.derby.impl.sql.catalog; + +import org.apache.derby.iapi.sql.dictionary.RoleGrantDescriptor; +import org.apache.derby.iapi.sql.dictionary.RoleClosureIterator; +import org.apache.derby.iapi.error.StandardException; +import java.util.List; +import java.util.HashMap; +import java.util.ArrayList; +import java.util.Iterator; + +/** + * Allows iterator over the role grant closure defined by the relation + * `GRANT` role-a `TO` role-b, or its inverse. + *

+ * The graph is represented as a `HashMap` where the key is + * the node and the value is a List grant descriptors representing + * outgoing arcs. The set constructed depends on whether `inverse` + * was specified in the constructor. + * @see org.apache.derby.iapi.sql.dictionary.RoleClosureIterator + */ +public class RoleClosureIteratorImpl implements RoleClosureIterator +{ + /** + * true if closure is inverse of GRANT role-a TO role-b. + */ + private final boolean inverse; + + /** + * Holds roles seen so far when computing the closure. + *

+ *
• Key: role name. Depending on value of {@code inverse}, the + * key represents and is compared against {@code roleName()} + * or {@code grantee()} of role descriptors visited.
• + *
• Value: none
• + *
+ */ + private HashMap seenSoFar; + + /** + * Holds the grant graph. + *
+ *
• key: role name
• + *
• value: list of {@code RoleGrantDescriptor}, making up outgoing arcs + * in graph
• + *