Avoid full attribute walk for types without subordinate types (#679)

Valery Kharseko

3 days ago f291f0a1baba3fa2ae4a6a856dd733e6a791318b

Avoid full attribute walk for types without subordinate types (#679)

 opendj-server-legacy/src/main/java/org/opends/server/types/Entry.java

@@ -34,6 +34,7 @@
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
@@ -663,9 +664,87 @@
    return Collections.emptyList();
  }

  /**
   * The set of attribute types having at least one subordinate type in a
   * schema, cached per schema instance. Subtype-inclusive attribute lookups
   * run for every entry read (compare assertions, search filters, password
   * policy attributes, ...): when the requested type has no subordinates,
   * walking every attribute of the entry degenerates to an exact map lookup,
   * so cache which types actually need the walk. The schema and the set
   * computed for it are held in one immutable holder swapped atomically, so
   * a reader can never pair a set with the wrong schema.
   */
  private static final class TypesWithSubordinates
  {
    private final Schema schema;
    private final Set<AttributeType> types;

    private TypesWithSubordinates(Schema schema, Set<AttributeType> types)
    {
      this.schema = schema;
      this.types = types;
    }
  }

  private static volatile TypesWithSubordinates typesWithSubordinates =
      new TypesWithSubordinates(null, Collections.<AttributeType> emptySet());

  private static boolean mayHaveSubordinateTypes(AttributeType attrType)
  {
    if (attrType.isPlaceHolder())
    {
      // isSuperTypeOf() matches place-holder types against schema-defined
      // types by name, which an exact map lookup cannot honor: keep the walk.
      return true;
    }
    Schema schema;
    try
    {
      schema = DirectoryServer.getInstance().getServerContext().getSchema();
    }
    catch (Exception e)
    {
      // No server schema available (offline tools, early startup):
      // conservatively assume subtypes may exist.
      return true;
    }
    if (schema == null)
    {
      return true;
    }
    TypesWithSubordinates cached = typesWithSubordinates;
    if (cached.schema != schema)
    {
      Set<AttributeType> withSubordinates = new HashSet<>();
      for (AttributeType type : schema.getAttributeTypes())
      {
        for (AttributeType superior = type.getSuperiorType(); superior != null;
            superior = superior.getSuperiorType())
        {
          withSubordinates.add(superior);
        }
      }
      cached = new TypesWithSubordinates(schema, withSubordinates);
      typesWithSubordinates = cached;
    }
    return cached.types.contains(attrType);
  }

  private void addAttributeTypeOrSubTypeValue(Collection<Attribute> results, AttributeType attrType,
      Map<AttributeType, List<Attribute>> attrsMap)
  {
    if (!mayHaveSubordinateTypes(attrType))
    {
      // No type in the schema extends attrType: isSuperTypeOf() can only
      // match the type itself, so use an exact lookup instead of walking
      // every attribute of the entry.
      List<Attribute> attributes = attrsMap.get(attrType);
      if (attributes != null)
      {
        results.addAll(attributes);
      }
      return;
    }
    for (Map.Entry<AttributeType, List<Attribute>> mapEntry : attrsMap.entrySet())
    {
      if (attrType.isSuperTypeOf(mapEntry.getKey()))
@@ -678,6 +757,21 @@
  private void addAttributeTypeOrSubTypeValue(Collection<Attribute> results, AttributeDescription attrDesc,
      Map<AttributeType, List<Attribute>> attrsMap)
  {
    if (!mayHaveSubordinateTypes(attrDesc.getAttributeType()))
    {
      List<Attribute> attributes = attrsMap.get(attrDesc.getAttributeType());
      if (attributes != null)
      {
        for (Attribute attribute : attributes)
        {
          if (attrDesc.isSuperTypeOf(attribute.getAttributeDescription()))
          {
            results.add(attribute);
          }
        }
      }
      return;
    }
    for (Map.Entry<AttributeType, List<Attribute>> mapEntry : attrsMap.entrySet())
    {
      if (!attrDesc.getAttributeType().isSuperTypeOf(mapEntry.getKey()))
@@ -697,6 +791,23 @@

  private boolean hasAttributeOrSubType(AttributeDescription attrDesc, Map<AttributeType, List<Attribute>> attrsMap)
  {
    if (!mayHaveSubordinateTypes(attrDesc.getAttributeType()))
    {
      List<Attribute> attributes = attrsMap.get(attrDesc.getAttributeType());
      if (attributes != null)
      {
        for (Attribute attribute : attributes)
        {
          // It's possible that there could be an attribute without any values,
          // which we should treat as not having the requested attribute.
          if (!attribute.isEmpty() && attrDesc.isSuperTypeOf(attribute.getAttributeDescription()))
          {
            return true;
          }
        }
      }
      return false;
    }
    for (Map.Entry<AttributeType, List<Attribute>> mapEntry : attrsMap.entrySet())
    {
      if (!attrDesc.getAttributeType().isSuperTypeOf(mapEntry.getKey()))