# FrameAstKey.java

    /*
    ** Module   : FrameAstKey.java
    ** Abstract : a dedicated key for comparing (shared) frames definitions
    **
    ** Copyright (c) 2016-2020, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- ---------------------------------Description---------------------------------
    ** 001 OM  20161121 Initial release.
    ** 002 CA  20200412 Added incremental conversion support.
    ** 003 CA  20200416 Reduce the memory footprint for incremental conversion.
    ** 004 CA  20200423 Keep a copy of the AST in memory, to not pin the entire file.
    ** 005 IAS 20200922 Get rid of possible NPE on serialization.
    */
    /*
    ** 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 com.goldencode.ast.*;
    import com.goldencode.p2j.pattern.*;

    /**
     * Objects of this class are used as keys for a hashtable that match frame definitions with
     * compatible structure that can be used by shared frames partitions. If two frames are compatible
     * then their {@code FrameAstKey} will be {@code equals}. If the keys are different, then the two
     * frames belong to different partitions.
     * <p>
     * The matching algorithm takes into consideration:
     * <ul>
     *    <li>type and name of all fields and variables used in FORM/FRAME definition;</li>
     *    <li>type of all literals from frame definition;</li>
     *    <li>the order of the above;</li>
     *    <li>the frame's name.</li>
     * </ul>
     * The matching algorithm does NOT take into consideration:
     * <ul>
     *    <li>spacers (SKIP and SPACE);</li>
     *    <li>the value of the literals;</li>
     *    <li>any form item in the HEADER definition;</li>
     *    <li>any declaration from any frame format node.</li>
     * </ul>
     */
    public class FrameAstKey
    implements Externalizable
    {
       /**
        * The Progress AST contained. It must be a {@code KW_FORM} or {@code DEFINE_FRAME} node.
        */
       private Aast fAst;

       /**
        * 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 name of the FRAME. This attribute is not mandatory. More frames can share the same
        * interface using different names, although this is rather strange. To have the code more
        * readable and consistent we enforce this constraint.
        */
       private String frameName;

       /**
        * Default c'tor, used for (de)serialization.
        */
       public FrameAstKey()
       {
          // no-op
       }

       /**
        * The single constructor. Saves a copy of the input data and computes the hash for quick match
        * as a hashing key.
        *
        * @param   ast
        *          The content node. Must be a {@code KW_FORM} or {@code DEFINE_FRAME}
        * @param   frameName
        *          The name of the frame. It cannot be always extracted directly form {@code ast}.
        *
        * @throws  NullPointerException
        *          if any argument is {@code null}.
        * @throws  RuntimeException
        *          on parameter validation failure: the first argument is not a FRAME definition
        *          ({@code KW_FORM} or {@code DEFINE_FRAME}).
        */
       public FrameAstKey(Aast ast, String frameName)
       {
          // ensure we detach the AST from the tree, to not keep the entire tree in the memory
          ast = ast.duplicate();
          initialize(ast, frameName);
       }

       /**
        * Obtain the hashing value for this container. This method is fast as the value was already
        * computed in constructor.
        *
        * @return  the hash value for this object.
        */
       @Override
       public int hashCode()
       {
          return hash;
       }

       /**
        * Check if another object {@code obj} and this are identical (represent FRAMES with compatible
        * structure, which can be SHARED). The algorithm iterates all relevant nodes from both
        * containers and try to match them. Like the hashing algorithm, only {@code FORM_ITEM} that
        * contains accessible information are taken into consideration (fields and variables). The
        * constants also add to hashing value but their actual value is not important. Spacers are
        * completely ignored.
        *
        * @param   obj
        *          A second object to test for item structure.
        *
        * @return  {@code true} if the {@code obj} and this contain compatible frame definitions.
        */
       @Override
       public boolean equals(Object obj)
       {
          if (!(obj instanceof FrameAstKey))
          {
             return false;
          }

          FrameAstKey that = (FrameAstKey) obj;

          if (!this.frameName.equals(that.frameName))
          {
             return false;
          }

          Aast ch = getNextSignificantNode((Aast) this.fAst.getFirstChild());
          Aast ch_ = getNextSignificantNode((Aast) that.fAst.getFirstChild());
          while (ch != null)
          {
             if (ch_ == null)
             {
                // [that] has more significant widgets
                return false;
             }

             // at this point ch and ch_ should both be ProgressParserTokenTypes.EXPRESSION
             Aast exprThis = (Aast) ch.getFirstChild();
             Aast exprThat = (Aast) ch_.getFirstChild();

             int thisType = exprThis.getType();
             if (thisType != exprThat.getType())
             {
                // the form item thisType does not match
                return false;
             }

             // in case of fields (TODO: and variables), check their names, too
             if ((thisType > ProgressParserTokenTypes.BEGIN_FIELDTYPES &&
                  thisType < ProgressParserTokenTypes.END_FIELDTYPES       ||
                  thisType > ProgressParserTokenTypes.BEGIN_VARTYPES   &&
                  thisType < ProgressParserTokenTypes.END_VARTYPES)            &&
                 !exprThis.getText().equals(exprThat.getText()))
             {
                return false;
             }

             ch = getNextSignificantNode((Aast) ch.getNextSibling());
             ch_ = getNextSignificantNode((Aast) ch_.getNextSibling());
          }

          return ch_ == null;
       }

       /**
        * Write this instance to stream.
        *
        * @param  out
        *         The object output stream.
        */
       @Override
       public void writeExternal(ObjectOutput out)
       throws IOException
       {
          writeLong(out, fAst == null ? null : fAst.getId());
          writeString(out, frameName);
       }

       /**
        * 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
       {
          Long astId = readLong(in);
          String frameName = readString(in);

          // TODO: if AST doesn't exist, don't initialize... throw exception?

          AstSymbolResolver resolver = AstSymbolResolver.getResolver();
          Aast ast = resolver.getAst(astId);
          if (ast == null)
          {
             AstManager mgr = AstManager.get();
             long treeId = mgr.getTreeId(astId);
             Aast tree = mgr.loadTree(mgr.getTreeName(treeId) + ".ast");
             resolver.registerTree(tree);
             ast = resolver.getAst(astId);
             resolver.deregisterTree(tree);
             ast = ast.duplicate();

             // re-register the tree so that other references to the same AST will re-use it
             resolver.registerTree(ast);
          }

          initialize(ast, frameName);
       }

       /**
        * Utility method that searches next relevant item from a frame definition, starting from a
        * current node, iterating its right siblings, until one is found or teh list ends.
        *
        * @param   frameDefNode
        *          the starting point for relevant node search.
        *
        * @return  a significant sibling if anyone is found or {@code null} otherwise.
        */
       private static Aast getNextSignificantNode(Aast frameDefNode)
       {
          while (frameDefNode != null)
          {
             switch (frameDefNode.getType())
             {
                case ProgressParserTokenTypes.KW_HEADER:
                   // from this point forward the widgets are not significant for comparing frame
                   // forms
                   return null;

                case ProgressParserTokenTypes.FORM_ITEM:
                   Aast ch2 = (Aast) frameDefNode.getFirstChild();
                   if (ch2.getType() == ProgressParserTokenTypes.EXPRESSION)
                   {
                      return frameDefNode;
                   }

                   // spacers are irrelevant, too: ProgressParserTokenTypes.KW_SPACE, KW_SKIP:
                   break;
             }

             // search next sibling node
             frameDefNode = (Aast) frameDefNode.getNextSibling();
          }

          // there are no more sibling nodes
          return null;
       }

       /**
        * Compute the hashing value for the FRAME component.
        * <p>
        * Iterate all nodes and create a hashing value for all relevant sub-nodes (the ones that are
        * needed for frame matching). Only {@code FORM_ITEM} that contains accessible information
        * are taken into consideration (fields and variables). The constants also add to hashing value
        * but their actual value is not important. Spacers are totally ignored.
        * <p>
        * The order is also important but it is not enforced directly. However, because of the way the
        * items are added and shifted sequentially, the result value should be sufficient for a
        * hashing key.
        *
        * @return  hashing value of this key.
        *
        * @throws  RuntimeException
        *          if some unexpected children are encountered.
        */
       private int computeHash()
       {
          int hash = frameName.hashCode();
          Aast ch = (Aast) fAst.getFirstChild();
          while (ch != null)
          {
             switch (ch.getType())
             {
                case ProgressParserTokenTypes.KW_HEADER:
                   // next elements (from the header) are irrelevant for our class
                   return hash;

                case ProgressParserTokenTypes.FORM_ITEM:
                   Aast ch2 = (Aast) ch.getFirstChild();
                   int ch2Type = ch2.getType();

                   if (ch2Type == ProgressParserTokenTypes.KW_SPACE ||
                       ch2Type == ProgressParserTokenTypes.KW_SKIP)
                   {
                      // spacers are irrelevant
                      break;
                   }

                   if (ch2Type == ProgressParserTokenTypes.EXPRESSION)
                   {
                      ch2 = (Aast) ch2.getFirstChild();
                      ch2Type = ch2.getType();
                   }

                   if (ch2Type > ProgressParserTokenTypes.BEGIN_FIELDTYPES &&
                       ch2Type < ProgressParserTokenTypes.END_FIELDTYPES       ||
                       ch2Type > ProgressParserTokenTypes.BEGIN_VARTYPES   &&
                       ch2Type < ProgressParserTokenTypes.END_VARTYPES)
                   {
                      hash = 37 * hash + ch2Type * 11 + ch2.getText().hashCode();
                   }
                   else
                   {
                      hash = 37 * hash + ch2Type;
                   }
                   break;

                case ProgressParserTokenTypes.FRAME_PHRASE:
                   // the elements under WITH keyword does not matter for this analyse
                   break;

                case ProgressParserTokenTypes.SYMBOL:
                case ProgressParserTokenTypes.KW_NEW:
                case ProgressParserTokenTypes.KW_SHARED:
                   if (ch.getParent() == fAst)
                   {
                      // in DEFINE [[NEW] SHARED] FRAME syntax this is normal, but we ignore the nodes
                      break;
                   }
                   throw new RuntimeException("Unexpected SYMBOL, NEW or SHARED token");

                default:
                   throw new RuntimeException("Unknown frame element: " +
                      ch.getSymbolicTokenType() + "(" + ch.getLine() + ":" + ch.getColumn() +")\n" +
                      fAst.dumpTree());
             }

             ch = (Aast) ch.getNextSibling();
          }
          return hash;
       }

       /**
        * Initialize this instance from the backing AST.
        *
        * @param   ast
        *          The content node. Must be a {@code KW_FORM} or {@code DEFINE_FRAME}
        * @param   frameName
        *          The name of the frame. It cannot be always extracted directly form {@code ast}.
        *
        * @throws  NullPointerException
        *          if any argument is {@code null}.
        * @throws  RuntimeException
        *          on parameter validation failure: the first argument is not a FRAME definition
        *          ({@code KW_FORM} or {@code DEFINE_FRAME}).
        */
      private void initialize(Aast ast, String frameName)
       {
          if (ast == null || frameName == null)
          {
             throw new NullPointerException("FORM and frame name must not be null.");
          }
          int aType = ast.getType();
          if (aType != ProgressParserTokenTypes.KW_FORM &&
              aType != ProgressParserTokenTypes.DEFINE_FRAME)
          {
             throw new RuntimeException("Invalid parameter. Not a form.");
          }
          this.fAst = ast;
          this.frameName = frameName;

          hash = computeHash();
       }
    }