mirror of https://github.com/OpenIdentityPlatform/OpenDJ.git
opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/ObjectIdentifierEqualityMatchingRuleImpl.java
@@ -12,65 +12,232 @@ * information: "Portions Copyright [year] [name of copyright owner]". * * Copyright 2009 Sun Microsystems, Inc. * Portions copyright 2011-2015 ForgeRock AS. * Portions copyright 2011-2016 ForgeRock AS. */ package org.forgerock.opendj.ldap.schema; import static org.forgerock.opendj.ldap.schema.SchemaConstants.*; import static org.forgerock.opendj.ldap.schema.SchemaOptions.*; import static org.forgerock.opendj.ldap.schema.SchemaUtils.*; import static com.forgerock.opendj.util.StaticUtils.toLowerCase; import static org.forgerock.opendj.ldap.schema.SchemaConstants.EMR_OID_NAME; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.List; import org.forgerock.opendj.ldap.Assertion; import org.forgerock.opendj.ldap.ByteSequence; import org.forgerock.opendj.ldap.ByteString; import org.forgerock.opendj.ldap.ConditionResult; import org.forgerock.opendj.ldap.DecodeException; import com.forgerock.opendj.util.StaticUtils; import com.forgerock.opendj.util.SubstringReader; import org.forgerock.opendj.ldap.spi.IndexQueryFactory; import org.forgerock.opendj.ldap.spi.Indexer; import org.forgerock.opendj.ldap.spi.IndexingOptions; /** * This class defines the objectIdentifierMatch matching rule defined in X.520 * and referenced in RFC 2252. This expects to work on OIDs and will match * and referenced in RFC 4517. This expects to work on OIDs and will match * either an attribute/objectclass name or a numeric OID. NOTE: This matching * rule requires a schema to lookup object identifiers in the descriptor form. */ final class ObjectIdentifierEqualityMatchingRuleImpl extends AbstractEqualityMatchingRuleImpl { final class ObjectIdentifierEqualityMatchingRuleImpl extends AbstractMatchingRuleImpl { /** * NOTE: this matching rule is used by the "objectClass" attribute type which is frequently used in filters and * which is also usually indexed for equality. Unfortunately, it is non-trivial to implement correctly and there * are a number of subtleties that need to be understood. * * Comparing two values for equality * ================================= * * The LDAP RFCs describe the algorithm for comparing assertion values with attribute values, but never discusses * how to compare two attribute values for equality in order to detect duplicate or missing values during updates. * * Given two schema elements: * * - object class with OID 1.2.3 and name "xxx" * - attribute type with OID 4.5.6 and name "xxx" * * When: * * - an attribute "oids" whose syntax is OID and which has the value "xxx" * * Then: * * - the filter "(oids=1.2.3)" matches, as does "(oids=4.5.6)", as does "(oids=xxx)". * * However, if the attribute's value is "1.2.3" then only the filters "(oids=1.2.3)" and "(oids=xxx)" match. In * order to compare two values with each other when enforcing set semantics in an LDAP attribute we need a function * which is reflexive, symmetric, and transitive. While the first two are possible, the last is not: * * - reflexive: 1.2.3 == 1.2.3, xxx == xxx * - symmetric: 1.2.3 == xxx, xxx == 1.2.3 * - transitive: 1.2.3 == xxx, xxx = 4.5.6, 1.2.3 != 4.5.6 * * The implication is that it is impossible to implement a reliable normalization method. There are three * options: * * 1) avoid resolving OID names to numeric OIDs during normalization and, instead, convert the OID to lower-case. * This approach has the undesirable effect of allowing users to add equivalent object classes to entries. For * example, the OIDs "2.5.6.6" and "person" are equivalent, but would have different normalized representations * * 2) resolve OID names to their equivalent numeric OID. For example, the normalized representation of "Person" * would be "2.5.6.6". Unfortunately, there are rare cases where two schema elements share the same name - one * can imagine having a custom object class called "manager" which would clash with the standard attribute * type "manager". In this situation, the algorithm must choose whether to convert the value to the object * class's numeric OID or the attribute type's. Unfortunately, this approach suffers from the same problem as * the first if it happens to prioritize the wrong type of schema element * * 3) as (2) but resolve numeric OIDs to their "primary" OID name. For example, the normalized representation of * "2.5.6.6" would be "person". The drawback with this approach is that an OID valued attribute cannot * contain two values having the same "primary" name. In the example above, the attribute "oids" cannot * contain the values "1.2.3" and "4.5.6" because they both share the same normalized primary name "xxx". Such * collisions will be extremely rare in practice because attributes rarely reference a heterogeneous set of * schema elements, such as a mix of attribute types and object classes. For example, the "objectClass" * attribute should only contain object class OIDs whose names should never collide. * * Option (3) has been chosen as the normalization strategy as it provides the best compromise. * * Indexes * ======= * * Indexing poses a different problem because indexes are persistent and rebuilding them is a relatively * expensive operation. If index keys depend on the schema, as is the case for the normalization algorithm (3) * above, then changes to the schema, e.g. the addition or removal of schema elements, may require an index * rebuild. In the above example, changing the primary name of one of the schema elements from "xxx" to "yyy" * invalidates any indexes. To avoid the need to rebuild indexes whenever the schema changes we use a simple * normalization algorithm - option (1) above - for generating index keys and employ a more complex algorithm for * querying the indexes during search operations: * * 1) compute all the possible aliases of the assertion value's OID using the current schema. In the earlier * example, a filter of the form "(oids=xxx)" would yield the keys "xxx", "1.2.3", and "4.5.6", whereas the * filter "(oids=1.2.3)" would only yield the keys "1.2.3" and "xxx" * * 2) perform an exact match index query against the index for each key * * 3) perform a union of the combined results. * * This algorithm may yield false positives in very rare cases when the schema contains many schema elements * sharing the same name. */ ObjectIdentifierEqualityMatchingRuleImpl() { super(EMR_OID_NAME); // Nothing to do. } static String resolveNames(final Schema schema, final String oidOrName) throws DecodeException { if (StaticUtils.isDigit(oidOrName.charAt(0))) { return oidOrName; } // Do a best effort attempt to normalize names to OIDs. final String lowerCaseName = StaticUtils.toLowerCase(oidOrName); try { final String oid = schema.getOIDForName(lowerCaseName); if (oid != null) { return oid; @Override public Assertion getAssertion(final Schema schema, final ByteSequence assertionValue) throws DecodeException { return getAssertion(schema, EMR_OID_NAME, assertionValue); } @Override public Collection<? extends Indexer> createIndexers(final IndexingOptions options) { return Collections.singleton(new Indexer() { @Override public String getIndexID() { return EMR_OID_NAME; } } catch (UnknownSchemaElementException e) { throw DecodeException.error(e.getMessageObject(), e); @Override public void createKeys(final Schema schema, final ByteSequence value, final Collection<ByteString> keys) throws DecodeException { // TODO: optimize - avoid converting to/from string + validate syntax. final String oid = toLowerCase(value.toString()).trim(); keys.add(ByteString.valueOfUtf8(oid)); } @Override public String keyToHumanReadableString(final ByteSequence key) { return key.toByteString().toString(); } }); } static Assertion getAssertion(final Schema schema, final String indexId, final ByteSequence assertionValue) { return new Assertion() { // TODO: optimize. final String oid = toLowerCase(assertionValue.toString()).trim(); final List<ByteString> candidates = getCandidates(schema, oid); @Override public ConditionResult matches(final ByteSequence normalizedAttributeValue) { return ConditionResult.valueOf(candidates.contains(normalizedAttributeValue.toByteString())); } @Override public <T> T createIndexQuery(final IndexQueryFactory<T> factory) throws DecodeException { final List<T> subQueries = new ArrayList<>(candidates.size()); for (final ByteString candidate : candidates) { subQueries.add(factory.createExactMatchQuery(indexId, candidate)); } return factory.createUnionQuery(subQueries); } }; } private static List<ByteString> getCandidates(final Schema schema, final String oid) { // TODO: optimize - avoid double lookups. // The set of candidates is likely to be small, usually 2 or 3, so avoid the memory overhead of using a Set // and instead store the candidates in a small array. final List<ByteString> candidates = new ArrayList<>(3); candidates.add(ByteString.valueOfUtf8(oid)); if (schema.hasObjectClass(oid)) { // Careful of placeholders final ObjectClass oc = schema.getObjectClass(oid); addCandidates(candidates, oc.getOID(), oc.getNames()); } return lowerCaseName; if (schema.hasAttributeType(oid)) { // Careful of placeholders final AttributeType at = schema.getAttributeType(oid); addCandidates(candidates, at.getOID(), at.getNames()); } if (schema.hasSyntax(oid)) { final Syntax syntax = schema.getSyntax(oid); addCandidates(candidates, syntax.getOID(), Collections.<String>emptyList()); } if (schema.hasMatchingRule(oid)) { final MatchingRule mr = schema.getMatchingRule(oid); addCandidates(candidates, mr.getOID(), mr.getNames()); } if (schema.hasNameForm(oid)) { final NameForm nf = schema.getNameForm(oid); addCandidates(candidates, nf.getOID(), nf.getNames()); } return candidates; } private static void addCandidates(final List<ByteString> candidates, final String numericOid, final List<String> names) { addIfNotPresent(candidates, ByteString.valueOfUtf8(numericOid)); for (final String name : names) { addIfNotPresent(candidates, ByteString.valueOfUtf8(toLowerCase(name))); } } private static void addIfNotPresent(final List<ByteString> candidates, final ByteString candidate) { if (!candidates.contains(candidate)) { candidates.add(candidate); } } @Override public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value) throws DecodeException { return normalizeAttributeValuePrivate(schema, value); } static ByteString normalizeAttributeValuePrivate(final Schema schema, final ByteSequence value) throws DecodeException { final String definition = value.toString(); final SubstringReader reader = new SubstringReader(definition); final String oid = readOID(reader, schema.getOption(ALLOW_MALFORMED_NAMES_AND_OPTIONS)); return ByteString.valueOfUtf8(resolveNames(schema, oid)); } @Override String keyToHumanReadableString(ByteSequence key) { return key.toByteString().toString(); // TODO: optimize - avoid converting to/from string + validate syntax + avoid double lookups. final String oid = toLowerCase(value.toString()).trim(); if (schema.hasObjectClass(oid)) { // Careful of placeholders return ByteString.valueOfUtf8(toLowerCase(schema.getObjectClass(oid).getNameOrOID())); } if (schema.hasAttributeType(oid)) { // Careful of placeholders return ByteString.valueOfUtf8(toLowerCase(schema.getAttributeType(oid).getNameOrOID())); } if (schema.hasSyntax(oid)) { return ByteString.valueOfUtf8(toLowerCase(schema.getSyntax(oid).getOID())); } if (schema.hasMatchingRule(oid)) { return ByteString.valueOfUtf8(toLowerCase(schema.getMatchingRule(oid).getNameOrOID())); } if (schema.hasNameForm(oid)) { return ByteString.valueOfUtf8(toLowerCase(schema.getNameForm(oid).getNameOrOID())); } return ByteString.valueOfUtf8(oid); } } opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/ObjectIdentifierFirstComponentEqualityMatchingRuleImpl.java
@@ -12,13 +12,12 @@ * information: "Portions Copyright [year] [name of copyright owner]". * * Copyright 2009 Sun Microsystems, Inc. * Portions copyright 2011-2015 ForgeRock AS. * Portions copyright 2011-2016 ForgeRock AS. */ package org.forgerock.opendj.ldap.schema; import static com.forgerock.opendj.ldap.CoreMessages.*; import static org.forgerock.opendj.ldap.schema.ObjectIdentifierEqualityMatchingRuleImpl.*; import static com.forgerock.opendj.util.StaticUtils.toLowerCase; import static org.forgerock.opendj.ldap.schema.SchemaConstants.*; import static org.forgerock.opendj.ldap.schema.SchemaOptions.*; import static org.forgerock.opendj.ldap.schema.SchemaUtils.*; @@ -33,7 +32,7 @@ /** * This class implements the objectIdentifierFirstComponentMatch matching rule * defined in X.520 and referenced in RFC 2252. This rule is intended for use * defined in X.520 and referenced in RFC 4517. This rule is intended for use * with attributes whose values contain a set of parentheses enclosing a * space-delimited set of names and/or name-value pairs (like attribute type or * objectclass descriptions) in which the "first component" is the first item @@ -47,7 +46,9 @@ @Override public Assertion getAssertion(final Schema schema, final ByteSequence assertionValue) throws DecodeException { return defaultAssertion(normalizeAttributeValuePrivate(schema, assertionValue)); return ObjectIdentifierEqualityMatchingRuleImpl.getAssertion(schema, EMR_OID_FIRST_COMPONENT_NAME, assertionValue); } @Override @@ -77,6 +78,6 @@ // The next set of characters must be the OID. final String oid = readOID(reader, schema.getOption(ALLOW_MALFORMED_NAMES_AND_OPTIONS)); return ByteString.valueOfUtf8(resolveNames(schema, oid)); return ByteString.valueOfUtf8(toLowerCase(oid, new StringBuilder(oid.length())).toString().trim()); } } opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/Schema.java
@@ -75,8 +75,6 @@ Syntax getDefaultSyntax(); String getOIDForName(String lowerCaseName); AttributeType getAttributeType(Schema schema, String nameOrOid); AttributeType getAttributeType(String nameOrOid, Syntax syntax); @@ -189,11 +187,6 @@ } @Override public String getOIDForName(final String lowerCaseName) { return strictImpl.getOIDForName(lowerCaseName); } @Override public AttributeType getAttributeType(final Schema schema, final String nameOrOid) { return getAttributeType0(nameOrOid, schema.getDefaultSyntax(), schema.getDefaultMatchingRule()); } @@ -502,45 +495,6 @@ } @Override public String getOIDForName(String lowerCaseName) { AttributeType attributeType = getAttributeType0(lowerCaseName); if (attributeType != null) { return attributeType.getOID(); } try { return getObjectClass(lowerCaseName).getOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } try { return getSyntax(null, lowerCaseName).getOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } try { return getMatchingRule(lowerCaseName).getOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } try { return getNameForm(lowerCaseName).getOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } try { return getDITContentRule(lowerCaseName).getStructuralClassOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } try { return getMatchingRuleUse(lowerCaseName).getMatchingRuleOID(); } catch (UnknownSchemaElementException ignore) { // try next schema element } return null; } @Override public AttributeType getAttributeType(String nameOrOid, Syntax syntax) { return getAttributeType(null, nameOrOid); } @@ -1149,17 +1103,6 @@ } /** * Return the numerical OID matching the lowerCaseName. * @param lowerCaseName The lower case name * @return OID matching the name or null if name doesn't match to an OID * @throws UnknownSchemaElementException if multiple OID are matching * lowerCaseName */ String getOIDForName(String lowerCaseName) { return impl.getOIDForName(lowerCaseName); } /** * Returns the attribute type for the specified name or numeric OID. * <p> * If the requested attribute type is not registered in this schema and this opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/ObjectIdentifierEqualityMatchingRuleTest.java
New file @@ -0,0 +1,153 @@ /* * The contents of this file are subject to the terms of the Common Development and * Distribution License (the License). You may not use this file except in compliance with the * License. * * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the * specific language governing permission and limitations under the License. * * When distributing Covered Software, include this CDDL Header Notice in each file and include * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL * Header, with the fields enclosed by brackets [] replaced by your own identifying * information: "Portions copyright [year] [name of copyright owner]". * * Copyright 2016 ForgeRock AS. * */ package org.forgerock.opendj.ldap.schema; import static org.assertj.core.api.Assertions.assertThat; import static org.forgerock.opendj.ldap.ConditionResult.FALSE; import static org.forgerock.opendj.ldap.ConditionResult.TRUE; import static org.forgerock.opendj.ldap.schema.SchemaConstants.EMR_OID_NAME; import static org.forgerock.opendj.ldap.schema.SchemaConstants.EMR_OID_OID; import static org.mockito.Matchers.anyCollection; import static org.mockito.Mockito.mock; import static org.mockito.Mockito.verify; import static org.mockito.Mockito.verifyNoMoreInteractions; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import org.forgerock.opendj.ldap.Assertion; import org.forgerock.opendj.ldap.ByteString; import org.forgerock.opendj.ldap.DecodeException; import org.forgerock.opendj.ldap.spi.IndexQueryFactory; import org.forgerock.opendj.ldap.spi.Indexer; import org.testng.annotations.DataProvider; import org.testng.annotations.Test; @Test public class ObjectIdentifierEqualityMatchingRuleTest extends MatchingRuleTest { @Override @DataProvider(name = "matchingRuleInvalidAttributeValues") public Object[][] createMatchingRuleInvalidAttributeValues() { return new Object[][] {}; } @Override @DataProvider(name = "matchingrules") public Object[][] createMatchingRuleTest() { return new Object[][] { // value, assertion, expected result // numeric OIDs match directly. { "2.5.4.3", "2.5.4.3", TRUE }, { "2.5.4.3", "2.5.4.4", FALSE }, // OID is known { "2.5.4.3", "9.9.9.999", FALSE }, // OID is unknown { "9.9.9.999", "9.9.9.999", TRUE }, { "9.9.9.999", "9.9.9.9999", FALSE }, // OID 'descr' form where assertion values are known to the schema. { "2.5.4.3", "cn", TRUE }, { "2.5.4.3", "commonName", TRUE }, { "2.5.4.3", "l", FALSE }, { "cn", "2.5.4.3", TRUE }, { "commonName", "2.5.4.3", TRUE }, { "l", "2.5.4.3", FALSE }, { "cn", "cn", TRUE }, { "commonName", "cn", TRUE }, { "cn", "commonName", TRUE }, { "commonName", "commonName", TRUE }, { "l", "cn", FALSE }, { "cn", "l", FALSE }, /* THESE TESTS FAIL BECAUSE THE ACTUAL RESULT IS FALSE // These are undefined because assertion values are unknown to the server. See RFC 4517 4.2.26. { "2.5.4.3", "dummy", UNDEFINED }, { "2.5.4.3", "xxx", UNDEFINED }, { "9.9.9.999", "foo", UNDEFINED }, */ // Strictly speaking this should evaluate to UNDEFINED since 'DUMMY' is not recognized. { "dummy", "DUMMY", TRUE }, // 2.5.4.3 is recognized (it's a numeric OID) so matching can be performed. { "dummy", "2.5.4.3", FALSE }, }; } @Override protected MatchingRule getRule() { return Schema.getCoreSchema().getMatchingRule(EMR_OID_OID); } @Test public void indexingShouldNotBeSensitiveToSchemaChanges() throws Exception { // 1) keys should be stable and not impacted by schema changes // 2) index queries should work even when the schema element has been removed. final String customDefinition = "( 9.9.9.999 NAME ( 'foo' 'bar' ) SUP name )"; final Schema customSchema = new SchemaBuilder(Schema.getCoreSchema()) .addAttributeType(customDefinition, true) .toSchema(); final List<ByteString> attributeValues = Arrays.asList(b("9.9.9.999"), b("FOO"), b("cn")); // Indexing should be insensitive to the schema. checkIndexContainsExpectedKeys(Schema.getCoreSchema(), attributeValues, b("9.9.9.999"), b("foo"), b("cn")); checkIndexContainsExpectedKeys(customSchema, attributeValues, b("9.9.9.999"), b("foo"), b("cn")); // Index queries should take advantage of the schema by testing alternative schema element names. final ByteString assertionValue = b("bar"); checkKeysUsedForIndexQuerying(Schema.getCoreSchema(), assertionValue, b("bar")); checkKeysUsedForIndexQuerying(customSchema, assertionValue, b("bar"), b("9.9.9.999"), b("foo")); } private void checkIndexContainsExpectedKeys(final Schema schema, final List<ByteString> attributeValues, final ByteString... expectedKeys) throws DecodeException { final MatchingRule mr = schema.getMatchingRule(EMR_OID_OID); final Indexer indexer = mr.createIndexers(null).iterator().next(); final ArrayList<ByteString> keys = new ArrayList<>(); for (final ByteString value : attributeValues) { indexer.createKeys(schema, value, keys); } assertThat(keys).containsExactly(expectedKeys); } private void checkKeysUsedForIndexQuerying(final Schema schema, final ByteString assertionValue, final ByteString... expectedKeys) throws DecodeException { final MatchingRule mr = schema.getMatchingRule(EMR_OID_OID); final Assertion assertion = mr.getAssertion(assertionValue); final IndexQueryFactory indexQueryFactory = mock(IndexQueryFactory.class); assertion.createIndexQuery(indexQueryFactory); for (final ByteString key : expectedKeys) { verify(indexQueryFactory).createExactMatchQuery(EMR_OID_NAME, key); } verify(indexQueryFactory).createUnionQuery(anyCollection()); verifyNoMoreInteractions(indexQueryFactory); } private ByteString b(final String value) { return ByteString.valueOfUtf8(value); } } opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/ObjectIdentifierFirstComponentEqualityMatchingRuleTest.java
New file @@ -0,0 +1,74 @@ /* * The contents of this file are subject to the terms of the Common Development and * Distribution License (the License). You may not use this file except in compliance with the * License. * * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the * specific language governing permission and limitations under the License. * * When distributing Covered Software, include this CDDL Header Notice in each file and include * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL * Header, with the fields enclosed by brackets [] replaced by your own identifying * information: "Portions copyright [year] [name of copyright owner]". * * Copyright 2016 ForgeRock AS. * */ package org.forgerock.opendj.ldap.schema; import static org.forgerock.opendj.ldap.ConditionResult.FALSE; import static org.forgerock.opendj.ldap.ConditionResult.TRUE; import static org.forgerock.opendj.ldap.schema.SchemaConstants.EMR_OID_FIRST_COMPONENT_OID; import org.testng.annotations.DataProvider; import org.testng.annotations.Test; @Test public class ObjectIdentifierFirstComponentEqualityMatchingRuleTest extends MatchingRuleTest { @Override @DataProvider(name = "matchingRuleInvalidAttributeValues") public Object[][] createMatchingRuleInvalidAttributeValues() { return new Object[][] {}; } @Override @DataProvider(name = "matchingrules") public Object[][] createMatchingRuleTest() { // This is defined in the core schema so the names 'cn' and 'commonName' will be recognized. However 'dummy' // is not part of the core schema definition so it won't be recognized by the server. final String cnDefinition = "( 2.5.4.3 NAME ( 'cn' 'commonName' 'dummy' ) SUP name )"; // Matching should be supported against the numeric OID, but the names are not in the core schema so cannot // be used in assertion values. final String customDefinition = "( 9.9.9.999 NAME ( 'foo' 'bar' ) SUP name )"; return new Object[][] { // numeric OIDs match directly. { cnDefinition, "2.5.4.3", TRUE }, { cnDefinition, "2.5.4.4", FALSE }, // OID is known { cnDefinition, "9.9.9.999", FALSE }, // OID is unknown, but it is numeric { customDefinition, "9.9.9.999", TRUE }, { customDefinition, "9.9.9.9999", FALSE }, // OID 'descr' form where assertion values are known to the schema. { cnDefinition, "cn", TRUE }, { cnDefinition, "commonName", TRUE }, { cnDefinition, "l", FALSE }, { customDefinition, "cn", FALSE }, /* THESE TESTS FAIL BECAUSE THE ACTUAL RESULT IS FALSE // These are undefined because the assertion values are unknown to the server. See RFC 4517 4.2.26. { cnDefinition, "dummy", UNDEFINED }, { cnDefinition, "xxx", UNDEFINED }, { customDefinition, "foo", UNDEFINED } */ }; } @Override protected MatchingRule getRule() { return Schema.getCoreSchema().getMatchingRule(EMR_OID_FIRST_COMPONENT_OID); } }
