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