# Namespace.java

    /*
    ** Module   : Namespace.java
    ** Abstract : A searchable Progress schema namespace
    **
    ** Copyright (c) 2004-2021, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- -----------------------------------Description-----------------------------------
    ** 001 ECF 20041223   @19172 Created initial version.
    ** 002 ECF 20050118   @19339 Added nodes() method to allow read-only
    **                           iteration over list of nodes in namespace,
    **                           for use by SchemaDictionary.
    ** 003 ECF 20050203   @19566 Added a parameter to the find method to
    **                           specify whether search must find an exact
    **                           match or an abbreviated one. This change was
    **                           made to allow SchemaDictionary to mimic the
    **                           actual symbol resolution performed by
    **                           Progress. Progress looks first for an exact
    **                           match in all scopes. Only if this fails are
    **                           all scopes searched again for an abbreviated
    **                           match.
    ** 004 ECF 20050207   @19627 Added the contains method and refactored the
    **                           various find methods, such that contains can
    **                           use the same underlying search algorithm.
    ** 005 ECF 20050209   @19733 Partially reverted search algorithm to
    **                           pre-003 (@19566) behavior, based on further
    **                           testing against live Progress source code.
    **                           However, retained the "exact" flag in find
    **                           method, which now allows an override of the
    **                           dual search (exact, then abbreviated match)
    **                           behavior to force exact match only.
    ** 006 ECF 20050221   @19900 Moved empty iterator implementation from
    **                           nodes() method into a standalone class:
    *                            com.goldencode.p2j.util.EmptyIterator.
    ** 007 ECF 20050413   @20706 Changed NameNode constructor called in find
    **                           method.
    ** 008 GES 20070402   @32703 Honor the preferred flag for a name node to
    **                           disambiguate an ambiguous name conflict. If
    **                           1 (and only 1) of the ambiguous name nodes
    **                           is marked as preferred, then match with that
    **                           node. Added a copy constructor.
    ** 009 GES 20071130   @36189 Allow nodes to be marked as maskable. Callers
    **                           obtaining an iterator can then choose if
    **                           the maskable nodes are or are not included
    **                           in the iterator.
    ** 010 ECF 20080730   @39271 Reduced memory footprint. Lazily initialize
    **                           collections of nodes and maskables. Use
    **                           smaller default sizes for these collections.
    ** 011 GES 20090421   @41831 Matched utility class package change.
    ** 012 ECF 20111217          Massive performance improvement: maintain sorting
    **                           of nodes list as nodes are added, rather than
    **                           using deferred sort.
    ** 013 CA  20130307          Fixed abbreviated field name disambiguation - the tables which are
    **                           weak reference in the current scope have precedence over others.
    ** 014 CA  20130524          Changed nodes(boolean, boolean) API to allow the result to be sorted.
    **                           Fix required for proper temp-table field ordering.
    ** 015 ECF 20130313          Added removeAll.
    ** 016 ECF 20160325          Fixed findPreferred, which would incorrectly disambiguate abbreviated
    **                           field names when more than one ambiguous match was in the preferred
    **                           (weak reference) set.
    ** 017 CA  20180404          CAN-FIND allows field abbreviations to be resolved even if ambiguous:
    **                           it will return the first field which matches the prefix.
    ** 018 ECF 20190620          EmptyIterator API change.
    ** 019 GES 20190518          Add disambiguation if only one match is strongly scoped to the
    **                           current scope.
    ** 020 ECF 20200825          Fixed NPE in removeAll method.
    **     OM  20211122          Added hints-based support for 'unloading' schema.
    */

    /*
    ** 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.schema;

    import java.util.*;
    import com.goldencode.util.*;

    /**
     * A namespace is used for unambiguous lookups of schema entity names. Objects
     * of this class are used by the {@link SchemaDictionary} to perform lookups
     * of schema entity (i.e., database, table, field) names within various
     * scopes.
     * <p>
     * A namespace contains a pool of {@link NameNode}s, each of which in turn
     * contains its own <code>Namespace</code> object. This hierarchy goes at most
     * three levels deep, reflecting the qualified name hierarchy represented by
     * the Progress language naming conventions for schema entity references:
     * <pre>
     *    database.table.field
     *    database.table
     *    table.field
     *    database
     *    table
     *    field
     * </pre>
     * where each part of a fully qualified name represents an entity which has
     * a one-to-many relationship with the entity to its right (if any), and a
     * one-to-one relationship with the entity to its left (if any).
     * <p>
     * Additional, global namespaces for lookups of unqualified database, table,
     * and field names are maintained by {@link SchemaDictionary}.
     * <p>
     * <code>Namespace</code> supports lookups of both unabbreviated and
     * abbreviated names. Whether abbreviation lookups are supported is determined
     * at construction. An exact match will always be preferred to an abbreviated
     * match. Only one exact match or one abbreviated match is permitted. If more
     * are detected, the search is considered ambiguous, and an exception will be
     * thrown by the {@link #findUnambiguously} method.
     */
    public class Namespace
    {
       /** Pool of name nodes comprising the namespace */
       private List<NameNode> nodes = null;

       /** Name nodes which can be excluded from the namespace iterator. */
       private Set<NameNode> maskable = null;

       /** Permit lookups using abbreviated names */
       private boolean abbreviations = false;

       /**
        * Constructor which sets abbreviated name lookup behavior.
        *
        * @param   abbreviations
        *          {@code true} to allow abbreviations, {@code false} to disallow.
        */
       public Namespace(boolean abbreviations)
       {
          this.abbreviations = abbreviations;
       }

       /**
        * Copy constructor which creates a separate and independent instance.
        *
        * @param   other
        *          The instance from which to pattern.
        */
       public Namespace(Namespace other)
       {
          this.abbreviations = other.abbreviations;

          if (other.nodes != null)
          {
             this.nodes = new ArrayList<>(other.nodes);
          }

          if (other.maskable != null)
          {
             this.maskable = new HashSet<>(other.maskable);
          }
       }

       /**
        * Add a name node to the namespace node pool at its naturally ordered
        * index (such that the pool is always sorted).
        *
        * @param   node
        *          Name node to be added to the pool.
        */
       public synchronized void add(NameNode node)
       {
          add(node, false);
       }

       /**
        * Add a name node to the namespace node pool at its naturally ordered
        * index (such that the pool is always sorted). Optionally mark the node as
        * one that can be excluded from iteration.
        *
        * @param   node
        *          Name node to be added to the pool.
        * @param   exclude
        *          <code>true</code> to mark this node as one that can be
        *          optionally excluded from an iterator.
        */
       public synchronized void add(NameNode node, boolean exclude)
       {
          if (nodes == null)
          {
             nodes = new ArrayList<>(1);
          }

          int index = Collections.binarySearch(nodes, node, NameNode.EXACT_COMPARATOR);
          if (index < 0)
          {
             index = -(index + 1);
          }

          nodes.add(index, node);

          if (exclude)
          {
             if (maskable == null)
             {
                maskable = new HashSet<>(4);
             }
             maskable.add(node);
          }
       }

       /**
        * Remove a name node from the namespace node pool and, if successful, set
        * a flag to indicate the list needs to be sorted. This method does not
        * actually re-sort the list (this is done lazily when a search is
        * performed).
        *
        * @param   node
        *          The node to be removed from the pool.
        *
        * @return  <code>true</code> if the node was removed; <code>false</code>
        *          if it was not present in the pool.
        */
       public synchronized boolean remove(NameNode node)
       {
          boolean success = false;

          if (nodes != null)
          {
             success = nodes.remove(node);

             // remove if it is there, we don't care about failures
             if (maskable != null)
             {
                maskable.remove(node);
             }

             if (success && nodes.size() == 0)
             {
                nodes = null;
             }
          }

          return success;
       }

       /**
        * Remove all name nodes from the namespace, except those specified.
        *
        * @param   except
        *          Set of name nodes to preserve.
        *
        * @return  A list of the name nodes removed from the namespace.
        */
       public synchronized List<NameNode> removeAll(Set<NameNode> except)
       {
          if (nodes == null || nodes.isEmpty())
          {
             return Collections.emptyList();
          }

          List<NameNode> removed = new ArrayList<>(nodes.size());

          Iterator<NameNode> iter = nodes.iterator();
          while (iter.hasNext())
          {
             NameNode node = iter.next();

             if (except.contains(node))
             {
                continue;
             }

             removed.add(node);

             iter.remove();
          }

          if (maskable != null && !removed.isEmpty())
          {
             maskable.removeAll(removed);
          }

          if (nodes.isEmpty())
          {
             nodes = null;
          }

          return removed;
       }

       /**
        * Get read-only iterator over ALL name nodes in this namespace. List is
        * sorted before the iterator returns.
        *
        * @return  Fail-fast iterator over the name node list.
        *
        * @throws  ConcurrentModificationException
        *          if the backing node list is modified while this iterator is
        *          in use.
        */
       public synchronized Iterator<NameNode> nodes()
       {
          return nodes(false);
       }

       /**
        * Get read-only iterator over the name nodes in this namespace. List is
        * sorted before the iterator returns.
        *
        * @param   exclude
        *          <code>true</code> to exclude nodes (marked as maskable) from
        *          the iterator. <code>false</code> to return all contained nodes.
        *
        * @return  Fail-fast iterator over the name node list.
        *
        * @throws  ConcurrentModificationException
        *          if the backing node list is modified while this iterator is
        *          in use.
        */
       public synchronized Iterator<NameNode> nodes(boolean exclude)
       {
          return nodes(exclude, false);
       }

       /**
        * Get read-only iterator over the name nodes in this namespace. List is
        * sorted before the iterator returns.
        *
        * @param   exclude
        *          <code>true</code> to exclude nodes (marked as maskable) from
        *          the iterator. <code>false</code> to return all contained nodes.
        * @param   sort
        *          Used only by fields; provide them by their ORDER clause. This must not affect the
        *          {@link #nodes()} list, thus it will return a copy.
        *
        * @return  Fail-fast iterator over the name node list.
        *
        * @throws  ConcurrentModificationException
        *          if the backing node list is modified while this iterator is
        *          in use.
        */
       public synchronized Iterator<NameNode> nodes(boolean exclude, boolean sort)
       {
          if (nodes == null)
          {
             // Return a do-nothing iterator.
             return EmptyIterator.get();
          }

          List<NameNode> subset = nodes;

          if (exclude && maskable != null)
          {
             subset = new ArrayList<>(nodes.size() - maskable.size());

             for (NameNode nn : nodes)
             {
                if (!maskable.contains(nn))
                {
                   subset.add(nn);
                }
             }
          }

          if (sort)
          {
             // do this in a copy, so we do not alter the namespace
             subset = new ArrayList<>(subset);
             Collections.sort(subset, new Comparator<NameNode>()
             {
                @Override
                public int compare(NameNode n1, NameNode n2)
                {
                   long o1 = n1.getOrder();
                   long o2 = n2.getOrder();

                   return o1 > o2 ? 1 : (o1 < o2 ? -1 : 0);
                }
             });
          }

          return Collections.unmodifiableList(subset).iterator();
       }

       /**
        * Indicate whether this namespace contains the specified name node.
        *
        * @param   node
        *          Name node for which to test.
        *
        * @return  <code>true</code> if node is found, else <code>false</code>.
        */
       public synchronized boolean contains(NameNode node)
       {
          return (find(node, NameNode.EXACT_COMPARATOR) >= 0);
       }

       /**
        * Find a name node with the specified name in the pool of nodes. This performs a lazy sort of the node
        * pool list if it is currently unsorted. This method attempts to find an exact match for the specified
        * name in this namespace. Then if not found and abbreviated matches are permitted by this instance, it
        * attempts to find an abbreviated match. If one (and only one) match is found, it is returned.
        *
        * @param   name
        *          Name for which to search (may be an unambiguous abbreviation for the target node's name if this
        *          namespace instance permits abbreviation lookups). Name may match no more than one node in this
        *          namespace.
        * @param   exact
        *          {@code true} to require an exact match; {@code false} to allow an exact or an abbreviated name
        *          to match.
        * @param   bannedSchemas
        *          The set of banned schemas. The {@code Namespace} will not recognize element from these schemas
        *          even is they are loaded.
        *
        * @return  The matching {@link NameNode} object from the node pool, if an unambiguous match was found, or
        *          {@code null} if no match was found. Also returns {@code null} if the internal pool of name
        *          nodes has not yet been initialized.
        *
        * @throws  AmbiguousSchemaNameException
        *          if {@code name} represents an ambiguous search key (i.e., matches more than one node in the
        *          pool) or if found to belong to banned schema.
        */
       public synchronized NameNode find(String name, boolean exact, Set<String> bannedSchemas)
       throws AmbiguousSchemaNameException
       {
          return find(name, exact, true, null, null, bannedSchemas);
       }

       /**
        * Find a name node with the specified name in the pool of nodes. This performs a lazy sort of the node
        * pool list if it is currently unsorted. This method attempts to find an exact match for the specified
        * name in this namespace. Then if not found and abbreviated matches are permitted by this instance, it
        * attempts to find an abbreviated match. If one (and only one) match is found, it is returned.
        *
        * @param   name
        *          Name for which to search (may be an unambiguous abbreviation for the target node's name if this
        *          namespace instance permits abbreviation lookups). Name may match no more than one node in
        *          this namespace.
        * @param   exact
        *          {@code true} to require an exact match;
        *          {@code false} to allow an exact or an abbreviated name to match.
        * @param   uniqueMatch
        *          Flag which forces an unique match when {@code exact} is {@code false}. If this is off, it will
        *          return the first matching field.
        * @param   preferred
        *          A set of priority nodes used to disambiguate abbreviated fields. This set is populated with the
        *          fields for the tables which have weak references. May be null.
        * @param   strong
        *          A set of priority nodes used to disambiguate in strong scopes. May be {@code null}.
        * @param   bannedSchemas
        *          The set of banned schemas. The {@code Namespace} will not recognize element from these schemas
        *          even is they are loaded.
        *
        * @return  The matching {@link NameNode} object from the node pool, if an unambiguous match was found, or
        *          {@code null} if no match was found. Also returns {@code null} if the internal pool of name
        *          nodes has not yet been initialized.
        *
        * @throws  AmbiguousSchemaNameException
        *          if {@code name} represents an ambiguous search key (i.e., matches more than one node in the
        *          pool) or if found to belong to banned schema.
        */
       public synchronized NameNode find(String        name,
                                         boolean       exact,
                                         boolean       uniqueMatch,
                                         Set<NameNode> preferred,
                                         Set<NameNode> strong,
                                         Set<String>   bannedSchemas)
       throws AmbiguousSchemaNameException
       {
          // No contents to search through.
          if (nodes == null)
          {
             return null;
          }

          NameNode key = new NameNode(name);

          // look for an exact match first
          NameNode found = findUnambiguously(key,
                                             NameNode.EXACT_COMPARATOR,
                                             preferred,
                                             strong,
                                             true,
                                             bannedSchemas);

          // if no exact match was found and abbreviations are allowed, look for an abbreviation match
          if (found == null && abbreviations && !exact)
          {
             found = findUnambiguously(key,
                                       NameNode.ABBREVIATION_COMPARATOR,
                                       preferred,
                                       strong,
                                       uniqueMatch,
                                       bannedSchemas);
          }

          return found;
       }

       /**
        * Find the name node in the pool which matches the specified search key, using {@code comparator} to
        * perform a binary search. If a match is found, test the nodes immediately before and after the found
        * node for matches using the same match criteria. If any are found, the search key is determined to be
        * ambiguous and an exception is thrown.
        *
        * @param   key
        *          Search key node used for comparison with nodes in the pool. Only the name stored in this key
        *          node is used in the search; other attributes are not considered and are therefore not
        *          necessary.
        * @param   comparator
        *          Comparator which is used to find a match in a binary search.
        * @param   preferred
        *          A set of priority nodes used to disambiguate abbreviated fields. This set is
        *          populated with the fields for the tables which have weak references. May be null.
        * @param   strong
        *          A set of priority nodes used to disambiguate in strong scopes. May be {@code null}.
        * @param   uniqueMatch
        *          Flag which forces a unique match when {@code exact} is {@code false}.
        *          If this is off, it will return the first matching field.
        * @param   bannedSchemas
        *          The set of banned schemas. The {@code Namespace} will not recognize element from these schemas
        *          even is they are loaded.
        *
        * @return  The matching {@code NameNode} object from the node pool, if an unambiguous match was found, or
        *          {@code null} if no match was found.
        *
        * @throws  AmbiguousSchemaNameException
        *          if the search key is ambiguous (i.e., matches more than one node in the pool) or if found to
        *          belong to banned schema.
        */
       private NameNode findUnambiguously(NameNode             key,
                                          Comparator<NameNode> comparator,
                                          Set<NameNode>        preferred,
                                          Set<NameNode>        strong,
                                          boolean              uniqueMatch,
                                          Set<String>          bannedSchemas)
       throws AmbiguousSchemaNameException
       {
          NameNode found = null;

          int index = find(key, comparator);
          if (index >= 0)
          {
             List<NameNode> matches = new LinkedList<>();

             NameNode node = nodes.get(index);
             if (isSchemaAvailable(node, bannedSchemas))
             {
                found = node;
                matches.add(node);
             }
             // else System.out.println("Found but not visible: " + node);

             // walk backward from index and check for duplicate matches
             boolean hit = true;
             for (int i = index - 1; hit && i >= 0; i--)
             {
                NameNode next = nodes.get(i);
                hit = (comparator.compare(next, key) == 0 && isSchemaAvailable(next, bannedSchemas));
                if (hit)
                {
                   if (matches.isEmpty())
                   {
                      found = next;
                   }
                   matches.add(next);
                }
             }

             // walk forward from index and check for duplicate matches
             hit = true;
             int size = nodes.size();
             for (int i = index + 1; hit && i < size; i++)
             {
                NameNode next = nodes.get(i);
                hit = (comparator.compare(next, key) == 0 && isSchemaAvailable(next, bannedSchemas));
                if (hit)
                {
                   if (matches.isEmpty())
                   {
                      found = next;
                   }
                   matches.add(next);
                }
             }

             if (matches.isEmpty())
             {
                return null;
             }

             // if more than one match, this search is ambiguous; throw an exception.
             int count = matches.size();
             if (count > 1)
             {
                // Try to disambiguate the name by checking if there is 1 (and
                // only 1) preferred node in the list. If so, return that node.
                found = findPreferred(matches, preferred);

                // try to disambiguate if only one of the matches is associated with the strong scope
                if (found == null && strong != null)
                {
                   found = findOverlap(matches, strong);
                }

                if (found == null)
                {
                   if (!uniqueMatch)
                   {
                      found = matches.get(0);

                      return found;
                   }

                   // the preferred flag didn't help. Abort
                   throw new AmbiguousSchemaNameException(
                         "'" + key.getName() + "' is ambiguous; " + count + " matches found", matches);
                }
             }
          }

          return found;
       }

       /**
        * Test whether a schema is available (I.e. it was not banned using hints).
        *
        * @param   schemaName
        *          The name of the schema to test.
        * @param   bannedSchemas
        *          The set of banned schemas. The {@code Namespace} will not recognize element from these schemas
        *          even is they are loaded.
        *
        * @return  {@code true} only if the schema is available and its element can be recognized in this
        *          namespace.
        */
       private boolean isSchemaAvailable(NameNode schemaName, Set<String> bannedSchemas)
       {
          if (bannedSchemas == null)
          {
             // no schema was banned
             return true;
          }

          return !bannedSchemas.contains(schemaName.getSchema());
       }

       /**
        * Returns the only match that is preferred or <code>null</code> if there
        * are no preferred matches or if there is more than 1 preferred match.
        *
        * @param   matches
        *          The list of all matches from which to find a preferred match.
        * @param   preferred
        *          A set of priority nodes used to disambiguate abbreviated fields. This set is
        *          populated with the fields for the tables which have weak references. May be null.
        *
        * @return  The match that is preferred or <code>null</code> if there is
        *          no single match that is preferred.
        */
       private NameNode findPreferred(List<NameNode> matches, Set<NameNode> preferred)
       {
          NameNode found = findOverlap(matches, preferred);

          if (found == null)
          {
             for (NameNode next : matches)
             {
                if (next.isPreferred())
                {
                   if (found == null)
                   {
                      // first preferred node
                      found = next;
                   }
                   else
                   {
                      // there is more than 1 preferred node, we are done
                      return null;
                   }
                }
             }
          }

          // if found is non-null, it must have been the only preferred match in the list
          return found;
       }

       /**
        * Returns the only match that is in the possible set or <code>null</code> if there are no
        * more possible matches or if there is more than 1 match.
        *
        * @param   matches
        *          The list of all matches from which to search from.
        * @param   possible
        *          A set of priority nodes used to disambiguate abbreviated fields. May be null.
        *
        * @return  The unique match that is in the possible set or <code>null</code> if there is
        *          no single match.
        */
       private NameNode findOverlap(List<NameNode> matches, Set<NameNode> possible)
       {
          if (possible != null)
          {
             List<NameNode> copyMatches = new ArrayList<>(matches);

             // check all matches to see if only one exists in the possible set
             if (copyMatches.retainAll(possible) && copyMatches.size() == 1)
             {
                // highlander (there can be only one)
                return copyMatches.get(0);
             }
          }

          return null;
       }

       /**
        * The actual implementation of the find node algorithm, this method lazily
        * sorts all name nodes in this namespace into their natural order, then
        * performs a binary search using <code>comparator</code>. If the list of
        * nodes has not yet been initialized at the time this method is invoked,
        * it returns <code>-1</code> immediately.
        * <p>
        * See also the java.util.Collections binarySearch method description.
        *
        * @param   key
        *          A name node whose name matches the target node.
        * @param   comparator
        *          Comparator which directs the binary search algorithm.
        *
        * @return  The index of a matching name node within the internal list
        *          <code>nodes</code>, or <code>-1</code> to indicate that the
        *          search found no match.
        */
       private int find(NameNode key, Comparator<NameNode> comparator)
       {
          // No contents to search through.
          if (nodes == null)
          {
             return -1;
          }

          return Collections.binarySearch(nodes, key, comparator);
       }
    }