# SortCriterion.java

    /*
    ** Module   : SortCriterion.java
    ** Abstract : Object which encapsulates a single "order by" sort criterion
    **
    ** Copyright (c) 2004-2024, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- -----------------------------------Description-----------------------------------
    ** 001 ECF 20060802   @28346 Created initial version. Based upon an inner
    **                           class previously within HQLHelper.
    ** 002 ECF 20060831   @29089 Added support for sorting by an indexed
    **                           property. Specifically, support sorting by
    **                           a property of a DMO's associated list of
    **                           composite properties.
    ** 003 ECF 20061120   @31328 Store DMO implementation class. This is the
    **                           class represented by a sort property's
    **                           qualifying alias in the order by clause.
    ** 004 ECF 20070216   @32169 Avoid directional mismatch if possible when
    **                           appending primary key as a sort criterion.
    **                           The primary key sort criterion's direction is
    **                           made to match that of the last explicit sort
    **                           criterion.
    ** 005 NVS 20070619   @34102 Fixed IndexOutOfBoundsException in parse()
    **                           method where the list was improperly modified
    **                           in a loop body.
    ** 006 ECF 20070705   @34363 Minor optimization. Replaced StringBuffer
    **                           with StringBuilder.
    ** 007 ECF 20070827   @34997 Handle temp table multiplex ID as a sortable
    **                           property.
    ** 008 ECF 20071130   @36125 Fixed redundant 'id' sort criterion. Only
    **                           append 'id' as sort criterion if not
    **                           redundant with explicit criteria, when
    **                           parsing a sort string.
    ** 009 ECF 20071205   @36262 Added toRawSortPhrase() method. This is used
    **                           by SortIndex when initializing a new
    **                           instance of that class.
    ** 010 ECF 20071218   @36462 Fixed handling of indexed sort criteria.
    **                           toRawSortPhrase() was producing an invalid
    **                           phrase in cases of indexed sort criteria.
    ** 011 ECF 20080310   @37486 Added support for computed columns. Computed
    **                           column property names are injected to replace
    **                           normal character property names as necessary.
    ** 012 ECF 20080330   @37739 Modified to support method change in
    **                           DatabaseManager.
    ** 013 SVL 20080418   @38035 makeUnique parameter added to parse().
    **                           doSpecificProcessing parameter added to
    **                           toSortExpression().
    ** 014 ECF 20080509   @38254 Fixed regression introduced by #011 (@37486).
    **                           Composite qualifiers were not being handled
    **                           correctly when generating sort and where
    **                           expressions.
    ** 015 ECF 20080510   @38502 Refactored to enable access from sub-package.
    **                           Made class and some methods public. Added new
    **                           parse() and ctor variants.
    ** 016 ECF 20080708   @39076 Added isPrimaryKey() method. Indicates if
    **                           sort criterion represents the backing table's
    **                           primary key.
    ** 017 ECF 20080924   @39937 Memory tuning. intern()'d strings which are
    **                           re-used within and across sessions.
    ** 018 SVL 20140210          Use HQLExpression instead of HQL string.
    ** 019 OM  20140410          Fixed support case-sensitive fields in indexes.
    ** 020 OM  20140623          DBUtils.composePropertyName() dialect aware support.
    ** 021 ECF 20150715          Minor refactoring to support compound query optimization.
    ** 022 OM  20151215          Fixed sorting NULL values for SQL Server dialect.
    ** 023 EVL 20160223          Javadoc fixes to make compatible with Oracle Java 8 for Solaris 10.
    ** 024 ECF 20160225          Simplified method lookup.
    ** 025 ECF 20160512          Added caching; eliminate interning of strings for short-lived
    **                           instances of this class.
    ** 026 ECF 20160524          Javadoc fix.
    ** 027 ECF 20160616          Replaced read-write cache lock with simple synchronization. Read lock
    **                           was not sufficient for calls to ExpiryCache.get, since it actually
    **                           updates the state of the cache.
    ** 028 OM  20160603          Fixed rtrimming to space character only.
    ** 029 OM  20171208          Added subscript in ANSI join and restrictor component. The method
    **                           toSortExpression() can generate unique aliases for usage in
    **                           subselects.
    ** 030 ECF 20171228          Minor performance improvement.
    ** 031 CA  20191009          Added where and sort clause translation in case of bound buffers.
    ** 032 CA  20191119          For non-null or datetimetz fields, toWhereExpression() must create a
    **                           WHERE clause which contains 'is null', when the next record is
    **                           retrieved in an ascending order (as 4GL sorts nulls high), and use
    **                           UDFs, in case of datetimetz fields.
    **     CA  20191211          The SortCriterion must know the database, to be able to use the
    **                           correct UDF, in case of datetime-tz fields.
    **     CA  20200117          Disabled the withNull in toWhereExpression, as this causes
    **                           regressions.
    ** 033 CA  20200120          Re-enabled withNull in toWhereExpression.
    ** 034 AIL 20200226          Fixed getAnsiJoin() for cases in which the alias had underscores.
    **     CA  20200306          Changed H033 to rely on 'WHERE_WITH_NULLS' system property, to
    **                           activate the 'withNull in toWhereExpression.
    ** 035 ECF 20200906          New ORM implementation.
    ** 036 OM  20201001          Dropped redundant ORDER BY elements in multi-table queries.
    **     OM  20201001          Improved DMO manipulation performance by caching slow Property annotation access.
    **     OM  20201007          Optimized SortCriterion by using DmoMeta data instead of map lookups. Simplified
    **                           API by dropping unneeded parameters. Optimized sort phrase parsing.
    **     ECF 20210506          Use RecordBuffer.getDmoInfo() getter instead of direct field access to
    **                           prevent NPE in proxy case.
    **     OM  20210704          Added specialized copy constructor.
    **     AL2 20220706          Added isCompatible to filter out the sort clauses not belonging to the buffer.
    **     OM  20220727          FieldId and PropertyId are different for denormalized extent fields.
    **     OM  20221103          New class names for FQLPreprocessor, FQLExpression, FQLBundle, and FQLCache.
    **     RAA 20230110          Reduced the number of iterations (for parsing the text) in constructor. Made
    **                           all non-final fields final.
    ** 037 DDF 20230608          Made the size of the cache configurable.
    **     DDF 20230613          Use CacheManager to initialize the cache.
    **     DDF 20230706          Replaced createLRUCache call with another one that will use a null
    **                           discriminator.
    ** 038 RAA 20231220          Rewrote a loop to be index-type.
    ** 039 SP  20240422          enabled withNull in toWhereExpression where there is an equality check
    **                           and WHERE_WITH_NULLS=false
    ** 040 CA  20240608          If a non-unique index is found for DMOSorter, force it to be unique by adding
    **                           the primary key as last component, using ascendent direction.  This is required
    **                           because when comparing a dirty record and a query found record, the order must
    **                           be on the primary key via pk, if the index is non-unique and both records are the
    **                           same otherwise.
    ** 041 CA  20240809          Cache the unqualified name.
    ** 042 TJD 20240705          Fix for sorting including NULLs/UNKNOWNS
    */

    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program is distributed in the hope that it will be useful,
    ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    ** GNU Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.persist;

    import java.lang.reflect.*;
    import java.util.*;
    import com.goldencode.cache.*;
    import com.goldencode.p2j.persist.dialect.*;
    import com.goldencode.p2j.persist.orm.*;

    /**
     * An individual sort criterion, consisting of a property name, sort
     * direction, DMO implementation class associated with an alias qualifier,
     * getter method for the property, and a flag indicating whether case is
     * ignored when sorting a <code>character</code> property.  Provides static
     * convenience methods to parse sort criteria and to produce an HQL-compliant
     * order by clause.
     * <p>
     * Two forms of the property name are stored:  the <code>name</code> and the
     * <code>orginalName</code>.  For non-indexed properties, these will be the
     * same.  For indexed properties, <code>name</code> is the expanded name
     * after considering the ANSI join needed to support the sort criterion;
     * <code>originalName</code> is the name as originally given before parsing.
     * For instance, the sort criterion <code>person.schedule[0] asc</code> would
     * have the following <code>name</code>:
     * <pre>
     *    person_composite5.schedule
     * </pre>
     * and the following <code>originalName</code>:
     * <pre>
     *    person.schedule[0]
     * </pre>
     * <p>
     * The from clause would be augmented with
     * <pre>
     *    ...join person.composite5 as person_composite5...
     * </pre>
     * and the where clause in this case would be augmented with
     * <pre>
     *    ...[and/where] index(person_composite5) = 0...
     * </pre>
     * <p>
     * Thus, given a DMO with a <code>schedule</code> field of extent 5, a basic
     * HQL statement of
     * <pre>
     *    from Person as person order by person.schedule[0] asc
     * </pre>
     * would be expanded to
     * <pre>
     *    from PersonImpl as person
     *    join person.composite5 as person_composite5
     *    where (index(person_composite5) = 0)
     *    order by person.empNum asc,
     *             upper(rtrim(person_composite5.schedule)) asc
     * </pre>
     * (assuming <code>schedule</code> is a case-insensitive character field of
     * extent 5).
     * <p>
     * Note that this class does not actually refactor the full HQL statement;
     * it provides the sort criteria helper methods that allow the various query
     * implementations to do so.
     */
    public final class SortCriterion
    {
       /** Flag indicating if the 'withNulls' is activated in {@link #toWhereExpression}. */
       private static final boolean WHERE_WITH_NULLS =
          "true".equalsIgnoreCase(System.getProperty("WHERE_WITH_NULLS"));

       /** Lock for cache */
       private static final Object cacheLock = new Object();

       /** Shared cache of immutable {@code SortCriterion} lists */
       private static ExpiryCache<CacheKey, List<SortCriterion>> cache;

       /** <code>true</code> if sort is ascending, else it is descending */
       private final boolean ascending;

       /** DMO implementation class containing the sort property */
       private final Class<? extends Record> dmoClass;

       /** Getter method associated with sort property */
       private final Method method;

       /** Is property of type character? */
       private final boolean isCharacter;

       /** Is case ignored (for character property only)? */
       private final boolean ignoreCase;

       /** Computed column prefix for property name (optional) */
       private final String computedColumnPrefix;

       /** DMO alias qualifier, if any */
       private final String alias;

       /** Unqualified property name */
       private final String propertyName;

       /** Sort property name, including subscript if any, usually qualified */
       private final String originalName;

       /** Sort property name, usually qualified */
       private final String name;

       /** Subscript value, if any */
       private final int subscript;

       /** Cache the unqualified name. */
       private final String unqualifiedName;

       /** SQL dialect which used this sort criterion; used for rtrim calls on character properties */
       private final Dialect dialect;

       /**
        * Constructor which parses original sort component text, deriving the property name, sort
        * direction, getter method for the property, case sensitivity of the property (character type
        * only), and possibly a subscript value (for extent fields) and a composite alias name (for
        * extent fields which are converted to use composite inner classes within the DMO).
        * <p>
        * This constructor should be used <strong>only</strong> for short-lived instances of this
        * class. It does not intern the numerous string fields (an expensive operation), so instances
        * created by this constructor should not be cached in memory, because the contents of these
        * strings will be duplicated many times.
        *
        * @param   buffer
        *          Record buffer.
        * @param   text
        *          Text representation of sort component, as provided by query.
        *
        * @throws  PersistenceException
        *          if there is any error with the text representation of the sort
        *          component provided by the caller.
        */
       SortCriterion(RecordBuffer buffer, String text)
       throws PersistenceException
       {
          this(buffer.getDialect(), text, buffer.getDmoInfo(), false);
       }

       /**
        * Constructor which parses original sort component text, deriving the
        * property name, sort direction, getter method for the property, case
        * sensitivity of the property (character type only), and possibly a
        * subscript value (for extent fields) and a composite alias name (for
        * extent fields which are converted to use composite inner classes within
        * the DMO).
        * <p>
        * This constructor should be used <strong>only</strong> for long-lived instances of this
        * class. It interns the numerous string fields (an expensive operation), so instances created
        * by this constructor can be cached in memory, without duplicating the contents of these
        * strings.
        *
        * @param   dialect
        *          Database dialect.
        * @param   text
        *          Text representation of sort component, as provided by query.
        * @param   dmoInfo
        *          Metadata for the table.
        *
        * @throws  PersistenceException
        *          if there is any error with the text representation of the sort
        *          component provided by the caller.
        */
       SortCriterion(Dialect dialect, String text, DmoMeta dmoInfo)
       throws PersistenceException
       {
          this(dialect, text, dmoInfo, true);
       }

       /**
        * Constructor which parses original sort component text, deriving the
        * property name, sort direction, getter method for the property, case
        * sensitivity of the property (character type only), and possibly a
        * subscript value (for extent fields) and a composite alias name (for
        * extent fields which are converted to use composite inner classes within
        * the DMO).
        *
        * @param   dialect
        *          Database dialect.
        * @param   text
        *          Text representation of sort component, as provided by query.
        * @param   dmoInfo
        *          Metadata for the table.
        * @param   internStrings
        *          {@code true} to intern string fields, else {@code false}.
        *
        * @throws  PersistenceException
        *          if there is any error with the text representation of the sort
        *          component provided by the caller.
        */
       SortCriterion(Dialect dialect, String text, DmoMeta dmoInfo, boolean internStrings)
       throws PersistenceException
       {
          this.dialect = dialect;
          this.dmoClass = dmoInfo.getImplementationClass();

          char[] src = text.toCharArray();
          int srcLength = src.length;
          boolean extentMode = false;

          // initially, this is set to the end-of-line position because we might not have a space.
          int spacePos = srcLength;
          int dotPos = -1;
          int bracketPos = -1;
          boolean reachedBracket = false;
          int subscriptBuilder = 0;

          for (int i = 0; i < srcLength; i++)
          {
             switch (src[i])
             {
                case '[':
                {
                   extentMode = true;
                   reachedBracket = true;
                   bracketPos = i;
                   break;
                }
                case ']':
                {
                   extentMode = false;
                   break;
                }
                case '.':
                {
                   dotPos = i;
                   break;
                }
                case ' ':
                {
                   spacePos = i;
                   break;
                }
             }

             if (extentMode && src[i] != '[')
             {
                subscriptBuilder = subscriptBuilder * 10 + (src[i] - '0');
             }
          }

          originalName = internStrings ? new String(src, 0, spacePos).intern() :
                                         new String(src, 0, spacePos);
          int length = (reachedBracket ? Math.min(bracketPos, spacePos) : spacePos) - dotPos - 1;
          propertyName = internStrings ?
                         new String(src, dotPos + 1, length).intern() :
                         new String(src, dotPos + 1, length);
          alias = internStrings ? new String(src, 0, dotPos).intern() :
                                  new String(src, 0, dotPos);
          name = internStrings ? new String(src, 0, dotPos + propertyName.length() + 1).intern() :
                                 new String(src, 0, dotPos + propertyName.length() + 1);
          subscript = reachedBracket ? subscriptBuilder : -1;
          unqualifiedName = propertyName + (subscript < 0 ? "" : "[" + subscript + "]");

          // if no space is found, then "asc" is implicit or
          // if the first character after the space is 'a', then "asc" is explicit;
          // otherwise, "desc" is found after the space.
          ascending = spacePos == srcLength || src[spacePos + 1] == 'a';

          DmoMeta dmoMeta = DmoMetadataManager.getDmoInfo(dmoClass);
          Property propMeta = dmoMeta.getFieldInfo(propertyName);

          // get backing getter method
          if (propMeta.propId == ReservedProperty.ID_MULTIPLEX)
          {
             method = null;
             isCharacter = false;
             ignoreCase = false;
             computedColumnPrefix = null;
          }
          else
          {
             String ccPrefix = null;
             method = propMeta.propId == ReservedProperty.ID_PRIMARY_KEY
                      ? PropertyHelper.allGettersByProperty(Persistable.class).get(propertyName)
                      : propMeta.annMethod;

             // determine case sensitivity and computed column prefix, if needed
             boolean caseSens = false;
             isCharacter = propMeta._isCharacter;
             if (isCharacter)
             {
                Boolean ccIgnoreCase = null;
                if (dialect.needsComputedColumns())
                {
                   ccIgnoreCase = dmoMeta.isIndexedIgnoreCase(propertyName);
                }

                if (ccIgnoreCase != null)
                {
                   caseSens = !ccIgnoreCase;
                   ccPrefix = dialect.getComputedColumnPrefix(caseSens);
                }
                else
                {
                   caseSens = propMeta.caseSensitive;
                }

                if (ccPrefix != null && internStrings)
                {
                   ccPrefix = ccPrefix.intern();
                }
             }
             ignoreCase = isCharacter && !caseSens;
             computedColumnPrefix = ccPrefix;
          }
       }

       /**
        * Specialized constructor which takes an existing {@code SortCriterion} and create a duplicate of it but
        * with changed alias. This is used when the buffer is bound (see {@code BIND} mode for table parameters)
        * under a different local variable name.
        *
        * @param   other
        *          The source {@code SortCriterion} to copy.
        * @param   alias
        *          The new alias to be used.
        */
       public SortCriterion(SortCriterion other, String alias)
       {
          this.dialect = other.dialect;
          this.propertyName = other.propertyName;
          this.subscript = other.subscript;
          this.unqualifiedName = other.unqualifiedName;
          this.ascending = other.ascending;
          this.dmoClass = other.dmoClass;
          this.method = other.method;
          this.isCharacter = other.isCharacter;
          this.ignoreCase = other.ignoreCase;
          this.computedColumnPrefix = other.computedColumnPrefix;
          this.alias = alias;
          this.originalName = other.originalName;
          this.name = alias + "." + propertyName +
                      (subscript < 0 ? "" : "[" + subscript + "]") + (ascending ? " asc" : " desc");
       }

       /**
        * Check if this sort clause contains a property of a specific DMO. The quantified table
        * should have the same name as the normalized legacy table.
        *
        * @param   sort
        *          An atomic sort clause containing a quantified property and optionally a sorting direction.
        * @param   dmoAlias
        *          The alias of the DMO against which the compatibility should be checked.
        *
        * @return  {@code true} if the provided sort clause related to the DMO.
        *
        * @throws  PersistenceException
        *          This is thrown when the formating itself is wrong. If the name is not quantified, it doesn't
        *          mean it is not compatible, but that the sort clause reached an illegal state.
        */
       public static boolean isCompatible(String sort, String dmoAlias)
       throws PersistenceException
       {
          int spacePos = sort.indexOf(' ');
          String rawName = ((spacePos != -1) ? sort.substring(0, spacePos) : sort).trim();
          int dotPos = sort.lastIndexOf(".");
          if (sort.lastIndexOf(".") < 0)
          {
             throw new PersistenceException("Sort property may not be unqualified:  " + rawName);
          }

          return sort.substring(0, dotPos).equals(dmoAlias);
       }

       /**
        * Initializes the cache using CacheManager. Only one cache is used,
        * so there is no need for a discriminator. The default value of the cache
        * is used when there is no size available from the configuration.
        */
       public static void initializeCache()
       {
          cache = CacheManager.createLRUCache(SortCriterion.class, 65536);
       }

       /**
        * Parse a sort phrase (not including the {@code "order by"} preamble) into a list of {@code SortCriterion}
        * objects. All components are recommended to be properties of the same DMO. Otherwise, the alias of
        * each sort component is checked.
        *
        * @param   dialect
        *          Database dialect.
        * @param   sort
        *          Sort phrase.
        * @param   dmoAlias
        *          Alias qualifier which represents DMO in sort phrase.
        * @param   dmoInfo
        *          Metadata for the table.
        * @param   makeUnique
        *          Indicates whether the {@code <dmoAlias>.recid} criterion should be appended to the returned
        *          criteria list.
        *
        * @return  List of {@code SortCriterion} objects.
        *
        * @throws  PersistenceException
        *          if there is any error parsing the given string.
        */
       public static List<SortCriterion> parse(Dialect dialect,
                                               String sort,
                                               String dmoAlias,
                                               DmoMeta dmoInfo,
                                               boolean makeUnique)
       throws PersistenceException
       {
          return parse(dialect, sort, dmoAlias, dmoInfo, makeUnique, false);
       }

       /**
        * Parse a sort phrase (not including the {@code "order by"} preamble) into a list of {@code SortCriterion}
        * objects. All components are recommended to be properties of the same DMO. Otherwise, the alias of
        * each sort component is checked.
        *
        * @param   dialect
        *          Database dialect.
        * @param   sort
        *          Sort phrase.
        * @param   dmoAlias
        *          Alias qualifier which represents DMO in sort phrase.
        * @param   dmoInfo
        *          Metadata for the table.
        * @param   makeUnique
        *          Indicates whether the {@code <dmoAlias>.recid} criterion should be appended to the returned
        *          criteria list.
        * @param   forceUniqueAsc
        *          Forces the recid to be asc, and not follow the last component direction, when 'makeUnique'.
        *
        * @return  List of {@code SortCriterion} objects.
        *
        * @throws  PersistenceException
        *          if there is any error parsing the given string.
        */
       public static List<SortCriterion> parse(Dialect dialect,
                                               String sort,
                                               String dmoAlias,
                                               DmoMeta dmoInfo,
                                               boolean makeUnique,
                                               boolean forceUniqueAsc)
       throws PersistenceException
       {
          CacheKey key = new CacheKey(dialect,
                                      sort,
                                      dmoAlias,
                                      dmoInfo.getImplementationClass(),
                                      makeUnique,
                                      forceUniqueAsc);
          List<SortCriterion> list = null;

          synchronized (cacheLock)
          {
             list = cache.get(key);
          }

          if (list != null)
          {
             return list;
          }

          boolean pKeyAscend = true;

          // Parse sort clause (if any).
          List<SortCriterion> sortCriteria = new LinkedList<>();
          Set<String> sortNames = new HashSet<>();
          if (sort != null && sort.trim().length() > 0)
          {
             SortCriterion next = null;
             String[] sortComponents = sort.split(",");
             for (int i = 0; i < sortComponents.length; i++)
             {
                // If the sort component is not compatible, it means it is for another DMO; just skip
                if (!isCompatible(sortComponents[i].trim(), dmoAlias))
                {
                   continue;
                }

                next = new SortCriterion(dialect, sortComponents[i].trim(), dmoInfo);
                String unqualifiedName = next.getUnqualifiedName();
                sortCriteria.add(next);
                sortNames.add(unqualifiedName);
             }

             // Match the primary key sort direction to that of the last sort criterion.
             if (next != null)
             {
                pKeyAscend = next.isAscending();
             }
          }

          // eliminate superfluous sort components if sort criteria define a superset of a unique
          // constraint.
          int size = sortCriteria.size();
          int lastUniqueComp = size;
          Iterator<Set<String>> uniques = dmoInfo.getUniqueConstraints().iterator();
          while (uniques.hasNext())
          {
             Set<String> compSet = uniques.next();
             if (sortNames.containsAll(compSet))
             {
                ListIterator<SortCriterion> iter = sortCriteria.listIterator(size);
                for (int j = size - 1; iter.hasPrevious(); j--)
                {
                   SortCriterion prev = iter.previous();
                   String name = prev.getUnqualifiedName();
                   if (!compSet.contains(name))
                   {
                      lastUniqueComp = Math.min(lastUniqueComp, j);
                      continue;
                   }

                   break;
                }
             }
             sortCriteria = sortCriteria.subList(0, lastUniqueComp);
             size = sortCriteria.size();
          }

          // Add primary key as the last component of the sort
          // criteria, if asked for it
          if (makeUnique && !sortNames.contains(DatabaseManager.PRIMARY_KEY))
          {
             String sortComp = dmoAlias + "." + DatabaseManager.PRIMARY_KEY + " " + (pKeyAscend ? "asc" : "desc");
             SortCriterion sortCrit = new SortCriterion(dialect, sortComp, dmoInfo);
             sortCriteria.add(sortCrit);
          }

          synchronized (cacheLock)
          {
             // check the cache again; if no other thread has added an entry for this key, add the
             // new list to the cache, otherwise return the list found in the cache
             list = cache.get(key);
             if (list == null)
             {
                list = Collections.unmodifiableList(sortCriteria);
                cache.put(key, list);
             }
          }

          return list;
       }

       /**
        * Parse a sort phrase (not including the &quot;order by&quot; preamble)
        * into a list of <code>SortCriterion</code> objects. All components are recommended to
        * be properties of the same DMO. Otherwise, the alias of each sort component is checked.
        *
        * @param   sort
        *          Sort phrase.
        * @param   buffer
        *          Record buffer associated with the sort phrase.
        *
        * @return  List of <code>SortCriterion</code> objects.  This list should
        *          never be empty;  even if <code>sort</code> is null or empty,
        *          a single criterion of <code>&lt;dmoAlias&gt;.recid</code> will be
        *          created.
        *
        * @throws  PersistenceException
        *          if there is any error parsing the given string.
        */
       public static List<SortCriterion> parse(String sort, RecordBuffer buffer)
       throws PersistenceException
       {
          return parse(sort, buffer, true);
       }

       /**
        * Parse a sort phrase (not including the &quot;order by&quot; preamble)
        * into a list of <code>SortCriterion</code> objects. All components are recommended to
        * be properties of the same DMO. Otherwise, the alias of each sort component is checked.
        *
        * @param   sort
        *          Sort phrase.
        * @param   buffer
        *          Record buffer associated with the sort phrase.
        * @param   makeUnique
        *          Indicates whether the <code>&lt;dmoAlias&gt;.recid</code>
        *          criterion should be appended to the returned criteria list.
        *
        * @return  List of <code>SortCriterion</code> objects.
        *
        * @throws  PersistenceException
        *          if there is any error parsing the given string.
        */
       static List<SortCriterion> parse(String sort, RecordBuffer buffer, boolean makeUnique)
       throws PersistenceException
       {
          return parse(sort, buffer, makeUnique, false);
       }

       /**
        * Parse a sort phrase (not including the &quot;order by&quot; preamble)
        * into a list of <code>SortCriterion</code> objects. All components are recommended to
        * be properties of the same DMO. Otherwise, the alias of each sort component is checked.
        *
        * @param   sort
        *          Sort phrase.
        * @param   buffer
        *          Record buffer associated with the sort phrase.
        * @param   makeUnique
        *          Indicates whether the <code>&lt;dmoAlias&gt;.recid</code>
        *          criterion should be appended to the returned criteria list.
        * @param   forceUniqueAsc
        *          Forces the recid to be asc, and not follow the last component direction, when 'makeUnique'.
        *
        * @return  List of <code>SortCriterion</code> objects.
        *
        * @throws  PersistenceException
        *          if there is any error parsing the given string.
        */
       static List<SortCriterion> parse(String sort, RecordBuffer buffer, boolean makeUnique, boolean forceUniqueAsc)
       throws PersistenceException
       {
          return parse(buffer.getDialect(), sort, buffer.getDMOAlias(), buffer.getDmoInfo(), makeUnique, forceUniqueAsc);
       }

       /**
        * Assemble an HQL &quot;order by&quot; clause, sans the &quot;order
        * by&quot; preamble, from the given list of sort criteria, optionally
        * inverting the sort direction of the sort criteria.
        *
        * @param   sortCriteria
        *          List of <code>SortCriterion</code> objects.
        * @param   invert
        *          <code>true</code> to reverse the sort direction of all sort
        *          criteria;  <code>false</code> to use the original sort
        *          directions of the sort criteria.
        *
        * @return  HQL order by clause, sans preamble.
        */
       static String assembleHQLNoPreamble(List<SortCriterion> sortCriteria, boolean invert)
       {
          StringBuilder buf = new StringBuilder();
          Iterator<SortCriterion> iter = sortCriteria.iterator();
          for (int i = 0; iter.hasNext(); i++)
          {
             SortCriterion next = iter.next();
             if (i > 0)
             {
                buf.append(", ");
             }
             buf.append(next.toSortExpression(invert, true, false, false));
          }

          return buf.toString();
       }

       /**
        * Generate a raw sort phrase from the given list of criteria, in the simple form:
        * <pre>
        *    {name} {direction} [, {name} {direction}]
        * </pre>
        * <p>
        * Character fields are not enclosed in any upper() or rtrim() functions.
        *
        * @param   sortCriteria
        *          List of sort criteria.
        *
        * @return  Raw sort phrase.
        */
       static String toRawSortPhrase(List<SortCriterion> sortCriteria)
       {
          StringBuilder buf = new StringBuilder();
          Iterator<SortCriterion> iter = sortCriteria.iterator();
          for (int i = 0; iter.hasNext(); i++)
          {
             SortCriterion next = iter.next();
             if (i > 0)
             {
                buf.append(", ");
             }
             buf.append(next.getOriginalName());
             buf.append(next.isAscending() ? " asc" : " desc");
          }

          return buf.toString();
       }

       /**
        * Get the unqualified name of the property backing this component.
        *
        * @return  Property name, sans DMO alias qualifier.
        */
       public String getUnqualifiedName()
       {
          return unqualifiedName;
       }

       /**
        * Get a normalized string representation of the sort component.  Uses the form:
        * <pre>
        *   {name} {direction}
        * </pre>
        * <p>
        * For example:
        * <pre>
        *   customer.accountNumber asc
        * </pre>
        * <p>
        * If this component represents a case-insensitive sort on a character property, the property
        * name will be enclosed in the <code>upper</code> database function, as in:
        * <pre>
        *   upper(customer.name) asc
        * </pre>
        *
        * @return  String representation as described above.
        */
       public String toString()
       {
          return toSortExpression(false);
       }

       /**
        * Indicate whether this sort criterion represents the DMO's primary key.
        *
        * @return  <code>true</code> if this sort criterion represents the DMO's
        *          primary key, else <code>false</code>.
        */
       boolean isPrimaryKey()
       {
          return DatabaseManager.PRIMARY_KEY.equals(propertyName);
       }

       /**
        * Get the name of the property behind this component.
        * <p>
        * This will usually be the same as the name returned by {@link
        * #getName()}, except in the case of an extent field.  In that case, this
        * method will return the name with the original subscripting.
        *
        * @return  Property name, usually qualified by DMO alias.
        */
       String getOriginalName()
       {
          return originalName;
       }

       /**
        * Get the DMO alias.
        *
        * @return    The DMO alias.
        */
       String getAlias()
       {
          return alias;
       }

       /**
        * Get the name of the property behind this component.
        * <p>
        * This will usually be the same as the name returned by {@link
        * #getOriginalName()}, except in the case of an extent field.  In that
        * case, this method will return the expanded name, in the form:
        * <pre>
        *    {alias}_composite{num}_{original_name_sans_subscript}
        * </pre>
        *
        * @return  Property name, usually qualified by DMO alias.
        */
       String getName()
       {
          return name;
       }

       /**
        * Indicate whether component sorts in ascending order.
        *
        * @return  <code>true</code> if ascending, <code>false</code> if
        *          descending.
        */
       boolean isAscending()
       {
          return ascending;
       }

       /**
        * Get the DMO implementation class containing the sort property for this criterion.
        *
        * @return  DMO implementation class.
        */
       Class<? extends Record> getDMOClass()
       {
          return dmoClass;
       }

       /**
        * Get the getter method associated with the property behind this component.
        *
        * @return  Getter method.
        */
       Method getMethod()
       {
          return method;
       }

       /**
        * Get a normalized string representation of the sort component.  Uses the form:
        * <pre>
        *   {name} {direction}
        * </pre>
        * <p>
        * For example:
        * <pre>
        *   customer.accountNumber asc
        * </pre>
        * <p>
        * If this component represents a case-insensitive sort on a character
        * property, the property name will be enclosed in the
        * <code>upper</code> database function, as in:
        * <pre>
        *   upper(customer.name) asc
        * </pre>
        * <p>
        * If the <code>invert</code> parameter is <code>true</code>, the sort
        * direction will be reversed, as in:
        * <pre>
        *   upper(customer.name) desc
        * </pre>
        *
        * @param   invert
        *          <code>true</code> to reverse the sort direction.
        *
        * @return  String representation as described above.
        */
       String toSortExpression(boolean invert)
       {
          return toSortExpression(invert, true, false, true);
       }

       /**
        * Get a normalized string representation of the sort component.  Uses the form:
        * <pre>
        *   {name} {direction}
        * </pre>
        * For example:
        * <pre>
        *   customer.accountNumber asc
        * </pre>
        * If this component represents a case-insensitive sort on a character property and
        * {@code doSpecificProcessing} is set, the property name will be enclosed in the {@code upper}
        * database function, as in:
        * <pre>
        *   upper(customer.name) asc
        * </pre>
        * If the {@code invert} parameter is {@code true}, the sort direction will be reversed, as in:
        * <pre>
        *   upper(customer.name) desc
        * </pre>
        *
        * @param   invert
        *          {@code true} to reverse the sort direction.
        * @param   useTableAlias
        *          {@code true} to qualify property names with aliases, else {@code false}.
        * @param   uniqueAlias
        *          if {@code true}, a unique alias will be generated for use in subselects.
        * @param   doSpecificProcessing
        *          {@code true} to perform dialect-specific processing (adding computed column prefix,
        *          string trimming and uppercasing)
        *
        * @return  String representation as described above.
        */
       String toSortExpression(boolean invert,
                               boolean useTableAlias,
                               boolean uniqueAlias,
                               boolean doSpecificProcessing)
       {
          //        Progress sort       MS SQL Server equivalent
          // ASC:   ASC + NULLS LAST    (CASE WHEN [Order] IS NULL THEN 1 ELSE 0 END), [Order] ASC
          // DESC:  DESC + NULLS FIRST  (CASE WHEN [Order] IS NULL THEN 0 ELSE 1 END), [Order] DESC

          boolean mssqlFix = dialect instanceof P2JSQLServer2008Dialect;
          StringBuilder buf = new StringBuilder();
          StringBuilder sortExpr = mssqlFix ? new StringBuilder() : null;

          if (!doSpecificProcessing)
          {
             if (mssqlFix)
             {
                sortExpr.append(originalName);
             }
             else
             {
                buf.append(originalName);
             }
          }
          else
          {
             String table = null;
             if (useTableAlias)
             {
                table = this.alias;
             }
             else if (uniqueAlias)
             {
                table =  DBUtils.getSubselectAlias(this.alias);
             }
             DBUtils.composePropertyName(isCharacter,
                                         ignoreCase,
                                         computedColumnPrefix,
                                         table,
                                         getUnqualifiedName(),
                                         mssqlFix ? sortExpr : buf,
                                         dialect);
          }

          if (mssqlFix)
          {
             String sorter = sortExpr.toString();
             buf.append("(case when ").append(sorter).append(" is null then ");
             buf.append(ascending ? "1" : "0").append(" else ");
             buf.append(ascending ? "0" : "1").append(" end), ").append(sorter);
          }

          buf.append(" ");
          if (invert)
          {
             buf.append(ascending ? "desc" : "asc");
          }
          else
          {
             buf.append(ascending ? "asc" : "desc");
          }

          return buf.toString();
       }

       /**
        * Get a string representation of this sort component which is suitable
        * to append to a base where clause when augmenting that where clause
        * to make it more specific.  The string represents an equality or
        * range match between the property name and a substitution parameter.
        * A range match may be inverted to represent the opposite sort
        * direction.  For example, the sort component
        * <pre>
        *   customer.accountNumber asc
        * </pre>
        * would be represented as:
        * <pre>
        *   customer.accountNumber = ?
        * </pre>
        * for an equality match;  as:
        * <pre>
        *   customer.accountNumber &gt; ?
        * </pre>
        * for a normal range match;  and as:
        * <pre>
        *   customer.accountNumber &lt; ?
        * </pre>
        * for an inverted range match.
        * <p>
        * Case-insensitive character properties are wrapped in the
        * <code>upper</code> database function, as in:
        * <pre>
        *   upper(customer.name) = ?
        * </pre>
        *
        * @param   rangeMatch
        *          <code>true</code> if a range match expression should be
        *          created;  <code>false</code> to create an equality match
        *          expression.
        * @param   invert
        *          <code>true</code> to reverse polarity of a range match
        *          expression, else <code>false</code>.
        *
        * @return  Where clause match expression as described above.
        */
       FQLExpression toWhereExpression(boolean rangeMatch, boolean invert)
       {
          // TODO: exclude non-null properties
          // TODO: this causes regressions in at least a case (see uast/raq_nulls_sort.p)
          boolean withNull = WHERE_WITH_NULLS ?
                             rangeMatch &&
                             (invert == !ascending) && !"id".equals(propertyName) :
                             !rangeMatch;

          StringBuilder buf = new StringBuilder();
          DBUtils.composePropertyName(isCharacter,
                                      ignoreCase,
                                      computedColumnPrefix,
                                      alias,
                                      getUnqualifiedName(),
                                      buf,
                                      dialect);
          String prop = buf.toString();
          String wherePart = (withNull) ? "(" + prop + " is null or " + prop : prop;

          FQLExpression whereClause = new FQLExpression(wherePart);
          if (rangeMatch)
          {
             if (invert)
             {
                whereClause.append(ascending ? " < " : " > ");
             }
             else
             {
                whereClause.append(ascending ? " > " : " < ");
             }
          }
          else
          {
             whereClause.append(" = ");
          }

          if (ignoreCase)
          {
             whereClause.append("upper(", true);
             whereClause.append(")");
          }
          else
          {
             whereClause.append("", true);
          }

          if (withNull)
          {
             whereClause.append(")");
          }

          return whereClause;
       }

       /**
        * Get a string representation of this sort component which is suitable
        * to append to a base where clause when augmenting that where clause
        * to make it more specific.  The string represents an equality or
        * range match between the property name and a substitution parameter.
        * A range match may be inverted to represent the opposite sort
        * direction. Match may also include check for NULL values, but as checking
        * for NULLS requires doubling of parameters it may be used only in
        * scenarios that support it.
        *
        * @param   rangeMatch
        *          <code>true</code> if a range match expression should be
        *          created;  <code>false</code> to create an equality match
        *          expression.
        * @param   invert
        *          <code>true</code> to reverse polarity of a range match
        *          expression, else <code>false</code>.
        * @param   withNull
        *          <code>true</code> to make check include NULLs in check
        *
        * @return  Where clause match expression as described above.
        */
       FQLExpression toWhereExpression(boolean rangeMatch, boolean invert, boolean withNull)
       {
          StringBuilder buf = new StringBuilder();
          DBUtils.composePropertyName(isCharacter,
                                      ignoreCase,
                                      computedColumnPrefix,
                                      alias,
                                      getUnqualifiedName(),
                                      buf,
                                      dialect);
          String prop = buf.toString();
          FQLExpression whereClause = new FQLExpression("");
          // final sort direction
          boolean sortAscending = ascending && ! invert || !ascending && invert;
          if (withNull)
          {
             whereClause.append("(coalesce(");
          }
          whereClause.append(prop);
          if (rangeMatch)
          {
             whereClause.append(sortAscending ? " > " : " < ");
          }
          else
          {
             whereClause.append(" = ");
          }

          if (ignoreCase)
          {
             whereClause.append("upper(", true);
             whereClause.append(")");
          }
          else
          {
             whereClause.append("", true);
          }
          if (withNull)
          {
             if (rangeMatch)
             {
                if (sortAscending)
                {
                   whereClause.append(", not (");
                   whereClause.append(prop);
                   whereClause.append(" = ");
                   whereClause.append(prop);
                   whereClause.append("), coalesce(", true);
                   whereClause.append(") is not null)");
                }
                else
                {
                   whereClause.append(", (");
                   whereClause.append(prop);
                   whereClause.append(" = ");
                   whereClause.append(prop);
                   whereClause.append("), false)");
                }
             }
             else
             {
                whereClause.append(", not (");
                whereClause.append(prop);
                whereClause.append(" = ");
                whereClause.append(prop);
                whereClause.append("), coalesce(", true);
                whereClause.append(") is null)");
             }
             whereClause.append(")");
          }

          return whereClause;
       }

       /**
        * Key for cached criterion lists.
        */
       private static class CacheKey
       {
          /** Database dialect */
          private final Dialect dialect;

          /** Sort phrase */
          private final String sort;

          /** DMO alias */
          private final String dmoAlias;

          /** DMO implementation class associated with {@code dmoAlias} */
          private final Class<? extends Record> dmoClass;

          /** Should sort criteria cause each record to be unique from a sorting perspective? */
          private final boolean makeUnique;

          /** Forces the recid to be asc, and not follow the last component direction, when {@link #makeUnique}. */
          private final boolean forceUniqueAsc;

          /** Cached hash code */
          private final int hashCode;

          /**
           * Constructor.
           *
           * @param   dialect
           *          Database dialect.
           * @param   sort
           *          Sort phrase.
           * @param   dmoAlias
           *          DMO alias.
           * @param   dmoClass
           *          DMO implementation class.
           * @param   makeUnique
           *          Should sort criteria cause each record to be unique from a sorting perspective?
           * @param   forceUniqueAsc
           *          Forces the recid to be asc, and not follow the last component direction, when 'makeUnique'.
           */
          private CacheKey(Dialect dialect,
                           String sort,
                           String dmoAlias,
                           Class<? extends Record> dmoClass,
                           boolean makeUnique,
                           boolean forceUniqueAsc)
          {
             this.dialect = dialect;
             this.sort = sort != null ? sort : "";
             this.dmoAlias = dmoAlias;
             this.dmoClass = dmoClass;
             this.makeUnique = makeUnique;
             this.forceUniqueAsc = forceUniqueAsc;
             this.hashCode = computeHash();
          }

          /**
           * Override of the default hash code algorithm. Consistent with {@link #equals(Object)}.
           *
           * @return  Hash code.
           */
          @Override
          public int hashCode()
          {
             return hashCode;
          }

          /**
           * Override of the default equivalence algorithm. Consistent with {@link #hashCode()}.
           *
           * return   {@code true} if this object is equivalent to the given object, else {@code
           *          false}.
           */
          @Override
          public boolean equals(Object o)
          {
             if (!(o instanceof CacheKey))
             {
                return false;
             }

             CacheKey that = (CacheKey) o;

             return (this.makeUnique == that.makeUnique &&
                     this.forceUniqueAsc == that.forceUniqueAsc &&
                     this.dialect.equals(that.dialect) &&
                     this.sort.equals(that.sort) &&
                     this.dmoAlias.equals(that.dmoAlias) &&
                     this.dmoClass.equals(that.dmoClass));
          }

          /**
           * Compute a hash code consistent with {@link #equals(Object)}.
           *
           * @return  Hash code.
           */
          private int computeHash()
          {
             int result = 17;
             result = 37 * result + dialect.hashCode();
             result = 37 * result + sort.hashCode();
             result = 37 * result + dmoAlias.hashCode();
             result = 37 * result + dmoClass.hashCode();
             result = 37 * result + (makeUnique ? 1 : 0);
             result = 37 * result + (forceUniqueAsc ? 1 : 0);

             return result;
          }
       }
    }