AstKey.java
/*
** Module : AstKey.java
** Abstract : a container for an AST which can be used as a hash key
**
** Copyright (c) 2006-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- ----------------Description-----------------
** 001 ECF 20060201 @24281 Created initial version. A container for an
** AST which can be used as a hashable key in a
** map or set.
** 002 ECF 20060407 @25422 Added token type wildcard support. Allows
** a set of comparison properties to be set with
** a wildcard key, such that it is these
** criteria which are used when an explicit set
** of criteria is not found for a particular
** token type.
** 003 GES 20090515 @42227 Moved to AstManager from AstRegistry/AstPersister.
** 004 CA 20200412 Added incremental conversion support.
** 005 CA 20200416 Reduce the memory footprint for incremental conversion.
** CA 20200423 Compute the hash only once. Also, keep a copy of the AST in memory,
** to not pin the entire file.
** 006 IAS 20200922 Get rid of possible NPE on serialization.
** TJD 20220504 Java 11 compatibility minor changes
** 007 CA 20230127 Performance improvement for incremental conversion.
** 008 CA 20230215 Fixed a bug in writeExternal - if the ast is null, write the astId, as the AST
** may not have needed to be loaded for this AstKey instance.
** 009 GBB 20230512 Logging methods replaced by CentralLogger/ConversionStatus.
*/
/*
** 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.uast;
import static com.goldencode.util.NativeTypeSerializer.*;
import java.io.*;
import java.util.*;
import java.util.logging.*;
import com.goldencode.ast.*;
import com.goldencode.p2j.convert.*;
import com.goldencode.p2j.pattern.*;
/**
* A container for an annotated AST which can be used as a hashable key in a
* hash map or hash set. This class overrides <code>equals()</code> and
* <code>hashCode</code> to provide implementations of these methods whose
* behavior is customizable, based upon criteria passed to the constructor.
* <p>
* Equality and hashing functionality is delegated to this separate class,
* rather than being hardcoded directly in the annotated AST implementation,
* because it is intended to operate on AST branches whose purpose and general
* structure is well known to the user. {@link AnnotatedAst}, on the other
* hand, is intended to be a very general purpose implementation.
* <p>
* Only those AST characteristics which are explicitly defined at
* instantiation are included in equality tests and hash code calculations.
* Characteristics which may be considered are token type, and optionally,
* within a specific token type, token text (either case sensitive or case
* insensitive), and zero or more annotation types. These are specified as
* a map that is passed to the constructor. The map's keys are token types.
* Each value is a collection containing zero or more annotation keys
* (Strings), and optionally, either a <code>true</code> or <code>false</code>
* value indicating the token's text (case insensitively or case sensitively,
* respectively) should be considered. The boolean values are mutually
* exclusive; only one may be included in the collection.
* <p>
* During processing of <code>equals()</code>, only those nodes whose token
* types appear in the map are tested for equality with the corresponding
* node in the comparison target. Other nodes are ignored completely, as if
* they did not exist. Likewise, annotations (and text) which are not
* included in the criteria are ignored. Thus, two ASTs that differ only in
* ignored token types, or text, or annotations, will be considered equal to
* one another. AST IDs are never considered, as these are required to be
* unique globally and would only match if an object were being compared with
* itself.
* <p>
* Likewise, <code>hashCode</code> considers only nodes, text, and annotations
* which are included in the criteria map when calculating its result.
* <p>
* Alternatively, a wildcard token type entry can be added to the map, such
* that the associated set of criteria are used when no more specific token
* type entry is found. This is done using the <code>KEY_WILDCARD</code>
* key to store criteria properties in the criteria map passed to this class'
* constructor. In this mode, <i>no nodes in either of the compared trees is
* ever ignored</i>. Thus, at a minimum, the token type structure of the two
* trees (plus any comparison properties specified) must be identical for two
* trees to be considered equal, or to have them generate the same hash code.
*/
public final class AstKey
implements Externalizable
{
/** Constant indicating that case insensitive text is a criterion */
public static final Boolean TEXT_KEY_IGNORE_CASE = Boolean.TRUE;
/** Constant indicating that case sensitive text is a criterion */
public static final Boolean TEXT_KEY_CASE_SENS = Boolean.FALSE;
/** Key which indicates the wildcard token type */
public static final Object KEY_WILDCARD = null;
/** Logger. */
private static final ConversionStatus LOG = ConversionStatus.get(AstKey.class);
/** AST whose data backs this key */
private Aast ast;
/** Map of token types to AST properties to consider */
private Map<Integer, Collection<?>> criteria = new LinkedHashMap<>();
/**
* Cached value of hash. {@code FrameAstKey} is imutabil so once computed in constructor it
* remains unchanged during the lifetime of the container.
*/
private int hash;
/** The serialized AST ID. */
private Long astId;
/**
* Default c'tor, used for (de)serialization.
*/
public AstKey()
{
}
/**
* Constructor which stores a backing AST and defines how this AST will be
* tested for equality with others, and how this key's hash code will be
* calculated.
*
* @param ast
* Backing data; may not be <code>null</code>
* @param criteria
* Map of token types to AST properties to consider for {@link
* #equals} and {@link #hashCode}; may not be <code>null</code>.
*/
public AstKey(Aast ast, Map<Integer, Collection<?>> criteria)
{
// ensure we detach the AST from the tree, to not keep the entire tree in the memory
ast = ast.duplicate();
initialize(ast, criteria);
}
/**
* A specialized equality test which checks only the subset of AST
* properties which were specified as criteria when this key was created.
* All other properties are ignored for purposes of this comparison.
*
* @param o
* Another object (presumably another instance of this class with
* identical test criteria) to test for equality with this one.
*
* @return <code>true</code> if <code>o</code> is considered equal to
* this object; else <code>false</code>.
*/
public final boolean equals(Object o)
{
if (this == o)
{
return true;
}
if (!(o instanceof AstKey))
{
return false;
}
AstKey that = (AstKey) o;
// Get depth-first iterators on each AST.
Iterator<Aast> thisIter = this.getAst().iterator();
Iterator<Aast> thatIter = that.getAst().iterator();
while (true)
{
Aast thisNext;
Aast thatNext;
Long thisIgnoreID = null;
Long thatIgnoreID = null;
// Skip as many nodes as needed if in an ignored branch.
do
{
thisNext = (thisIter.hasNext() ? (Aast) thisIter.next() : null);
if (thisNext != null)
{
// If token type is not specified in criteria map, ignore this
// branch.
if (!criteria.containsKey(Integer.valueOf(thisNext.getType())) &&
!criteria.containsKey(KEY_WILDCARD))
{
// System.out.println("* Ignoring this " + thisNext.getPath());
thisIgnoreID = thisNext.getId();
continue;
}
/*
if (isIgnoreNode(thisNext, thisIgnoreID))
{
System.out.println(" Ignoring this " + thisNext.getPath());
}
*/
}
}
while (thisNext != null && isIgnoreNode(thisNext, thisIgnoreID));
// Skip as many nodes as needed if in an ignored branch.
do
{
thatNext = (thatIter.hasNext() ? (Aast) thatIter.next() : null);
if (thatNext != null)
{
// If token type is not specified in criteria map, ignore this
// branch.
if (!criteria.containsKey(Integer.valueOf(thatNext.getType())) &&
!criteria.containsKey(KEY_WILDCARD))
{
// System.out.println("* Ignoring that " + thatNext.getPath());
thatIgnoreID = thatNext.getId();
continue;
}
/*
if (isIgnoreNode(thatNext, thatIgnoreID))
{
System.out.println(" Ignoring that " + thatNext.getPath());
}
*/
}
}
while (thatNext != null && isIgnoreNode(thatNext, thatIgnoreID));
// We must reach the end of both trees simultaneously if they are to
// be considered equal.
if (thisNext == null || thatNext == null)
{
return (thisNext == thatNext);
}
// Token types must match.
int thisType = thisNext.getType();
int thatType = thatNext.getType();
if (thisType != thatType)
{
return false;
}
// Other properties (annotations and possibly text) must match.
Set<?> props = (Set<?>) criteria.get(Integer.valueOf(thisType));
if (props == null)
{
props = (Set<?>) criteria.get(KEY_WILDCARD);
}
if (!(compareNodes(thisNext, thatNext, props)))
{
return false;
}
}
}
/**
* Calculates a hash code for this key, which is consistent with this
* class' implementation of {@link #equals}. That is, two objects
* considered equal according to the <code>equals</code> method will
* always produce identical hash codes by this method.
*
* @return Hash code for this AST key instance.
*/
public final int hashCode()
{
return hash;
}
/**
* Determine whether the specified node should be ignored. A node is
* ignored if <code>ignoreID</code> is not <code>null</code> AND
* <code>ignoreID</code> matches its ID or any of its parents' IDs.
*
* @param node
* Node under test.
* @param ignoreID
* ID which demarcates an ignored branch of nodes.
*
* @return <code>true</code> if <code>node</code> should be ignored;
* else <code>false</code>.
*/
private boolean isIgnoreNode(Aast node, Long ignoreID)
{
if (ignoreID == null)
{
return false;
}
Aast next = node;
while (next != null)
{
if (next.getId().equals(ignoreID))
{
return true;
}
next = next.getParent();
}
return false;
}
/**
* Determine whether two nodes are considered equal to one another based
* upon a comparison of only the specified subset of their common
* properties. It is assumed their token types have been matched before
* this method is invoked.
*
* @param x
* First node.
* @param y
* Second node.
* @param props
* Set of properties to test for equality.
*
* @return <code>true</code> if nodes test as equal, else
* <code>false</code>
*/
private boolean compareNodes(Aast x, Aast y, Set<?> props)
{
if (props == null)
{
return true;
}
Iterator<?> iter = props.iterator();
while (iter.hasNext())
{
Object next = iter.next();
if (TEXT_KEY_IGNORE_CASE.equals(next))
{
if (!x.getText().equalsIgnoreCase(y.getText()))
{
return false;
}
}
else if (TEXT_KEY_CASE_SENS.equals(next))
{
if (!x.getText().equals(y.getText()))
{
return false;
}
}
else if (!compareAnnotations(x, y, (String) next))
{
return false;
}
}
return true;
}
/**
* Determine whether the given nodes have the same value for an annotation.
* In the case of a list value, the nodes must have the same number of
* entries in both nodes and all entries in the list must compare as equal.
* If the annotation is not present in both nodes, the test passes
* successfully.
*
* @param x
* First node.
* @param y
* Second node.
* @param key
* Annotation key.
*
* @return <code>false</code> if the annotation is not present in either
* (but not both) nodes, or if its value differs between nodes;
* else <code>true</code>.
*/
private boolean compareAnnotations(Aast x, Aast y, String key)
{
int lenX = x.annotationSize(key);
int lenY = y.annotationSize(key);
if (lenX != lenY)
{
return false;
}
if (lenX == 0)
{
Object valX = x.getAnnotation(key);
Object valY = y.getAnnotation(key);
if (valX == null || valY == null)
{
return (valX == valY);
}
return valX.equals(valY);
}
for (int i = 0; i < lenX; i++)
{
Object valX = x.getAnnotation(key, i);
Object valY = y.getAnnotation(key, i);
if (((valX == null || valY == null) && valX != valY) ||
!valX.equals(valY))
{
return false;
}
}
return true;
}
/**
* Calculate a hash code for the given node, which considers only those
* properties specified in <code>props</code>.
*
* @param node
* Node whose properties are used to calculate the hash code.
* @param props
* A set of annotation keys and/or one of the special text keys.
*
* @return Hash code for <code>node</code>.
*/
private int hashCode(Aast node, Set<?> props)
{
int result = 17;
if (props == null)
{
return result;
}
Iterator<?> iter = props.iterator();
while (iter.hasNext())
{
Object next = iter.next();
if (TEXT_KEY_IGNORE_CASE.equals(next))
{
result = 37 * result + node.getText().toLowerCase().hashCode();
}
else if (TEXT_KEY_CASE_SENS.equals(next))
{
result = 37 * result + node.getText().hashCode();
}
else
{
result = 37 * result + annotationsHashCode(node, (String) next);
}
}
return result;
}
/**
* Calculate the hash code for a particular annotation on the given AST
* node. If the annotation is a list, the combined hash code for all
* list elements is calculated.
*
* @param node
* Target AST.
* @param key
* Annotation key.
*
* @return Hash code for the annotation value(s) at the given key.
*/
private int annotationsHashCode(Aast node, String key)
{
int result = 17;
int len = node.annotationSize(key);
if (len == 0)
{
if (node.isAnnotation(key))
{
result = 37 * result + node.getAnnotation(key).hashCode();
}
}
else
{
for (int i = 0; i < len; i++)
{
result = 37 * result + node.getAnnotation(key, i).hashCode();
}
}
return result;
}
/**
* Write this instance to stream.
*
* @param out
* The object output stream.
*/
@Override
public void writeExternal(ObjectOutput out)
throws IOException
{
writeLong(out, ast == null ? astId : ast.getId());
out.writeObject(criteria);
out.writeInt(hash);
}
/**
* Restore this instance by re-loading the AST with the given ID and {@link #initialize} it.
*
* @param in
* The object input stream.
*/
@Override
public void readExternal(ObjectInput in)
throws IOException,
ClassNotFoundException
{
this.astId = readLong(in);
this.criteria = (Map<Integer, Collection<?>>) in.readObject();
this.hash = in.readInt();
}
/**
* Calculates a hash code for this key, which is consistent with this
* class' implementation of {@link #equals}. That is, two objects
* considered equal according to the <code>equals</code> method will
* always produce identical hash codes by this method.
*
* @return Hash code for this AST key instance.
*/
private int computeHash()
{
int result = 17;
Long ignoreID = null;
Iterator<Aast> iter = ast.iterator();
while (iter.hasNext())
{
Aast next = iter.next();
Integer tokenType = Integer.valueOf(next.getType());
// Skip this node if it is within an ignored branch.
if (isIgnoreNode(next, ignoreID))
{
// System.out.println(" Ignoring " + next.getPath());
continue;
}
// Reset ignore ID if we are not within an ignored branch.
ignoreID = null;
// If token type is not specified in criteria map, ignore this
// branch.
if (!criteria.containsKey(tokenType) &&
!criteria.containsKey(KEY_WILDCARD))
{
// System.out.println("* Ignoring " + next.getPath());
ignoreID = next.getId();
continue;
}
Set<?> props = (Set<?>) criteria.get(tokenType);
if (props == null)
{
props = (Set<?>) criteria.get(KEY_WILDCARD);
}
result = 37 * result + hashCode(next, props);
}
// System.out.println("Hash code for " + this + ": " + result);
return result;
}
/**
* Initialize this instance using the backing AST.
*
* @param ast
* Backing data; may not be <code>null</code>
* @param criteria
* Map of token types to AST properties to consider for {@link
* #equals} and {@link #hashCode}; may not be <code>null</code>.
*/
private void initialize(Aast ast, Map<Integer, Collection<?>> criteria)
{
if (ast == null || criteria == null)
{
throw new NullPointerException();
}
this.ast = ast;
Iterator<Map.Entry<Integer, Collection<?>>> iter = criteria.entrySet().iterator();
while (iter.hasNext())
{
Map.Entry<Integer, Collection<?>> next = iter.next();
Integer tokenType = (Integer) next.getKey();
@SuppressWarnings("rawtypes")
Set props = null;
Collection<?> c = next.getValue();
if (c != null)
{
props = new LinkedHashSet<>();
props.addAll(c);
}
this.criteria.put(tokenType, props);
}
hash = computeHash();
}
/**
* Resolve the {@link #ast} if is not yet resolved.
* <p>
* This will load into the {@link AstSymbolResolver} the entire tree associated with the {@link #astId}.
*
* @return The {@link #ast}.
*/
private Aast getAst()
{
if (this.ast != null)
{
return this.ast;
}
// TODO: if AST doesn't exist, don't initialize... throw exception?
AstSymbolResolver resolver = AstSymbolResolver.getResolver();
ast = resolver.getAst(astId);
if (ast == null)
{
AstManager mgr = AstManager.get();
long treeId = mgr.getTreeId(astId);
Aast tree = mgr.loadTree(mgr.getTreeName(treeId));
resolver.registerTree(tree.duplicate());
ast = resolver.getAst(astId);
}
return ast;
}
/**
* Test harness. Runs <code>equals</code> and <code>hashCode</code>
* methods against two P2O ASTs.
*
* @param args
* Two filenames are expected (the persisted ASTs to be loaded).
*/
public static void main(String[] args)
{
try
{
Aast x = AstManager.get().loadTree(args[0]);
Aast y = AstManager.get().loadTree(args[1]);
Map<Integer,Collection<?>> test = new HashMap<>();
List<Object> props = new ArrayList<>();
props.add(TEXT_KEY_IGNORE_CASE);
test.put(Integer.valueOf(ProgressParserTokenTypes.DATABASE), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.TEMP_TABLE), null);
test.put(Integer.valueOf(ProgressParserTokenTypes.WORK_TABLE), null);
props = new ArrayList<>();
props.add(TEXT_KEY_IGNORE_CASE);
props.add("label");
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_INT), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_DEC), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_DATE), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_CHAR), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_LOGICAL), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.FIELD_RAW), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.KW_INIT), null);
props = new ArrayList<>();
props.add(TEXT_KEY_IGNORE_CASE);
test.put(Integer.valueOf(ProgressParserTokenTypes.STRING), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.NUM_LITERAL), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.DEC_LITERAL), props);
test.put(Integer.valueOf(ProgressParserTokenTypes.DATE_LITERAL), props);
props = new ArrayList<>();
props.add("unique");
test.put(Integer.valueOf(ProgressParserTokenTypes.INDEX), props);
props = new ArrayList<>();
props.add("descend");
props.add("case-sensitive");
test.put(Integer.valueOf(ProgressParserTokenTypes.INDEX_FIELD), props);
/*
props.add(TEXT_KEY_CASE_SENS);
test.put(KEY_WILDCARD, props);
*/
AstKey kx = new AstKey(x, test);
AstKey ky = new AstKey(y, test);
System.out.println("kx.equals(ky): " + (kx.equals(ky)));
System.out.println("kx.hashCode(): " + kx.hashCode());
System.out.println("ky.hashCode(): " + ky.hashCode());
}
catch (Exception exc)
{
LOG.log(Level.SEVERE, "", exc);
}
}
}