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);
}
}