# RelationAnalyzer.java

    /*
    ** Module   : RelationAnalyzer.java
    ** Abstract : Analyzes natural relations between database table pairs
    **
    ** Copyright (c) 2005-2023, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- -----------------------------------Description-----------------------------------
    ** 001 ECF 20050325   @20997 Created initial version. Detects natural join
    **                           relations between two database tables in a
    **                           Progress schema. Capable of scanning a schema
    **                           and reporting all potential relations.
    ** 002 ECF 20050623   @21606 Minor fix to support change in schema AST
    **                           structure. The unique designation for an
    **                           index was moved from a descendant node to an
    **                           annotation.
    ** 003 ECF 20051005   @22982 Back out #002 (@21606). Side effect of schema
    **                           fixups ruleset change.
    ** 004 ECF 20081216   @40937 Fixed findJoiningIndex(). This method did not
    **                           properly handle temp-table indexes, which can
    **                           have multiple PROPERTIES tags.
    ** 005 GES 20090518   @42399 Import change.
    ** 006 ECF 20131013          Added new type of relation analysis for metadata tables. Implemented
    **                           generics.
    ** 007 ECF 20131215          Fixed metadata table relation analysis.
    ** 008 TJD 20220504          Java 11 compatibility minor changes
    ** 009 GBB 20230512          Logging methods replaced by CentralLogger/ConversionStatus.
    ** 010 OM  20230630          Added support for the newly observed PARENT_ID_RELATION between joined tables.
    */

    /*
    ** 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 java.util.logging.*;

    import com.goldencode.ast.*;
    import com.goldencode.p2j.cfg.*;
    import com.goldencode.p2j.convert.*;

    /**
     * Examines implicit relations between database tables following Progress
     * rules for table joins.  Specifically:
     * <ul>
     * <li>the tables must have between them one or more field with a common name
     *     and data type;
     * <li>the common field(s) must participate in a unique index in at least
     *     one of the tables;
     * <li>only one such relationship between the two tables is allowed.
     * </ul>
     *
     * Note that this definition only covers <em>natural joins</em> between
     * tables which would be analagous to primary-foreign key relations in a
     * relational database.  Explicit joins which do not follow the rules above
     * are certainly possible in Progress source code, where any fields of the
     * same data type in two tables can be used as an ad-hoc relation in a
     * query.  The analysis performed by this class <em>does not</em> cover
     * these types of ad-hoc joins.
     */
    class RelationAnalyzer
    implements SchemaParserTokenTypes
    {
       /** Logger */
       private static final ConversionStatus LOG = ConversionStatus.get(RelationAnalyzer.class);

       /** Names of metadata tables involved in conversion */
       private Set<String> metaTables;

       /** Schema dictionary which is consulted for schema information */
       private SchemaDictionary dictionary = null;

       /**
        * Constructor which accepts the schema dictionary to consult for schema
        * information while analyzing relations.
        *
        * @param   dictionary
        *          Schema dictionary.
        */
       RelationAnalyzer(SchemaDictionary dictionary)
       {
          this.dictionary = dictionary;
          this.metaTables = Configuration.getSchemaConfig().getMetadata().getTables();
       }

       /**
        * Get a list of trees, each of which is composed of {@link RelationNode}
        * objects. The root of each tree represents a Progress database table
        * which has no dependencies on any other table. The children of each
        * node represent tables which each have a foreign key relation to the
        * parent node's table. Note that the nodes within each tree may be
        * duplicated across trees.
        *
        * @param   joins
        *          A set of {@link TableRelation} objects that each represent a
        *          natural join between a pair of Progress tables.
        *
        * @return  List of relation node trees as described above.
        */
       List<RelationNode> analyze(Set<TableRelation> joins)
       {
          Map<Aast, Collection<TableRelation>> nodeMap =
             new LinkedHashMap<Aast, Collection<TableRelation>>();
          Set<Aast> foreigns = new HashSet<Aast>();

          Iterator<TableRelation> iter = joins.iterator();
          while (iter.hasNext())
          {
             TableRelation relation = iter.next();
             Aast primary = relation.getPrimary();

             if (primary == null)
             {
                LOG.log(Level.WARNING, "Ambiguous relation: " + relation);

                continue;
             }

             Collection<TableRelation> nodes = nodeMap.get(primary);
             if (nodes == null)
             {
                nodes = new ArrayList<TableRelation>();
             }
             nodes.add(relation);
             foreigns.add(relation.getRight());
             nodeMap.put(primary, nodes);
          }

          ArrayList<RelationNode> roots = new ArrayList<RelationNode>();
          Iterator<Aast> iter2 = nodeMap.keySet().iterator();
          while (iter2.hasNext())
          {
             Aast next = iter2.next();
             if (!foreigns.contains(next))
             {
                RelationNode root = createTree(nodeMap, next, null);
                roots.add(root);
             }
          }

          roots.trimToSize();

          return roots;
       }

       /**
        * Debug method to dump to <code>stdout</code> the hierarchy of relations
        * defined by <code>node</code>.
        *
        * @param   node
        *          Starting node for the tree dump. Descendent nodes are walked
        *          recursively.
        */
       void dumpTree(RelationNode node)
       {
          Iterator<RelationNode> iter = (Iterator<RelationNode>) node.descendantsIterator();
          while (iter.hasNext())
          {
             RelationNode next = iter.next();
             System.out.println(next.toString());
          }
       }

       /**
        * Get a set of all <em>potential</em> {@linkplain TableRelation natural
        * relations} between two tables, based upon the schema data only (not on
        * references within source code).
        *
        * @param   database
        *          Name of database to scan for potential relations.
        *
        * @return  Set of all potential, natural table relations.
        */
       Set<TableRelation> getAllRelations(String database)
       {
          List<Aast> list = new LinkedList<>();
          Set<TableRelation> set = new TreeSet<>();
          Set<String> noJoins = new TreeSet<>();
          Set<Aast> rights = new HashSet<>();

          // Get initial list of tables.
          Iterator<Aast> iter = dictionary.tables(database);
          while (iter.hasNext())
          {
             list.add(iter.next());
          }

          Iterator<Aast> iter2 = list.iterator();
          while (iter2.hasNext())
          {
             Aast left = iter2.next();
             iter2.remove();
             boolean hit = false;

             Iterator<Aast> iter3 = list.iterator();
             while (iter3.hasNext())
             {
                Aast right = iter3.next();
                TableRelation join = attemptNaturalJoin(left, right);
                if (join != null)
                {
                   set.add(join);
                   hit = true;
                   rights.add(right);
                }
             }

             if (!hit && !rights.contains(left))
             {
                noJoins.add(left.getText());
             }
          }

          System.out.println("NO RELATIONS:");
          System.out.println("-------------");
          Iterator<String> iter4 = noJoins.iterator();
          while (iter4.hasNext())
          {
             String next = iter4.next();
             System.out.println("No potential relations for table: " + next);
          }

          return set;
       }

       /**
        * Create a table relation object which describes the <em>natural
        * join</em> relation between two tables. Such a relation is defined by
        * the two tables having at least one field of a common name and data
        * type, which participates in a unique index in one of the tables.
        * <p>
        * Although there is no concept of primary and foreign keys in Progress,
        * we determine, if possible, how the two tables in a natural join would
        * fall into these categories. If only one of the two tables has an index
        * which meets the requirement defined above, that table is considered
        * the "primary" end of the natural join; the other table is considered
        * the "foreign" end. If both tables contain an index which meets the
        * requirement, it is ambiguous as to how the tables can be mapped into
        * a primary-foreign key relationship with one another.
        *
        * @param   left
        *          The left-hand table in the potential join.
        * @param   right
        *          The right-hand table in the potential join.
        *
        * @return  The table relation object which defines the possible, natural
        *          relation between the two tables.
        *
        * @throws  SchemaException
        *          if a natural join of the two tables is not possible.
        */
       TableRelation createJoin(String left, String right)
       throws SchemaException
       {
          Aast t1 = dictionary.getTable(left);
          Aast t2 = dictionary.getTable(right);

          TableRelation join = attemptNaturalJoin(t1, t2);
          if (join == null)
          {
             // try parent-recid relation, except for temp-tables
             join = attemptParentIdJoin(t1, t2);

             if (join == null)
             {
                throw new SchemaException("Invalid join: " + left + " of " + right);
             }
          }

          return join;
       }

       /**
        * Attempt to determine a potential, <em>parent-id join</em> between the two tables specified. For such a
        * join to be possible, none of the tables should be temporary, and the child table must have a RECID
        * field whose name has the following pattern {@code <parent-table-name>-recid[<suffix>]}. if there are
        * multiple fields with this naming schema, the one with shorter suffix is chosen, best match being when
        * the suffix is empty/missing.
        *
        * @param   t1
        *          The left-hand (parent) table in the potential join.
        * @param   t2
        *          The right-hand (child) table in the potential join.
        *
        * @return  The table relation object which defines the possible, parent-id relation between the two tables,
        *          or {@code null} if no such relation is possible.
        */
       private TableRelation attemptParentIdJoin(Aast t1, Aast t2)
       {
          if (false || (t1.getType() == TEMP_TABLE || t2.getType() == TEMP_TABLE))
          {
             return null;
          }

          String parentRecidPattern = t1.getText().toLowerCase() + "-recid";
          Aast childField = (Aast) t2.getFirstChild();
          Aast bestCandidate = null; // this will be used when multiple fields have [parentRecidPattern] as prefix
          while (childField != null)
          {
             if (childField.getType() == FIELD_RECID)
             {
                String childFieldName = childField.getText().toLowerCase();
                if (childFieldName.equals(parentRecidPattern))
                {
                   // found /parent-recid/ field
                   return new TableRelation(t1,
                                            t2,
                                            t1,
                                            new HashSet<>(Collections.singleton(childField.getText())),
                                            PARENT_ID_RELATION);
                }
                if (childFieldName.startsWith(parentRecidPattern) &&
                    (bestCandidate == null || bestCandidate.getText().compareTo(childField.getText()) > 0))
                {
                   bestCandidate = childField;
                }
             }
             childField = (Aast) childField.getNextSibling();
          }

          if (bestCandidate != null)
          {
             // use the best candidate for /parent-recid/ field
             return new TableRelation(t1,
                                      t2,
                                      t1,
                                      new HashSet<>(Collections.singleton(bestCandidate.getText())),
                                      PARENT_ID_RELATION);
          }

          return null;
       }

       /**
        * Attempt to determine a potential, <em>natural join</em> between the
        * two tables specified. For a natural join to be possible, the tables
        * must both define at least one field with the same name and data type,
        * which participates in a unique index in at least one of the
        * tables. More than one field may meet these criteria. Only one index
        * per table may meet these criteria, but that restriction is not
        * enforced here.
        * <p>
        * Alternatively, if the tables are metadata tables, attempt to determine
        * a primary-foreign key join.
        * <p>
        * Although there is no concept of primary and foreign keys in Progress,
        * we determine, if possible, how the two tables in a natural join would
        * fall into these categories. If only one of the two tables has an index
        * which meets the requirement defined above, that table is considered
        * the "primary" end of the natural join; the other table is considered
        * the "foreign" end. If both tables contain an index which meets the
        * requirement, it is ambiguous as to how the tables can be mapped into
        * a primary-foreign key relationship with one another.
        *
        * @param   left
        *          The left-hand table in the potential join.
        * @param   right
        *          The right-hand table in the potential join.
        *
        * @return  The table relation object which defines the possible, natural relation between the two tables,
        *          or {@code null} if no such relation is possible.
        */
       private TableRelation attemptNaturalJoin(Aast left, Aast right)
       {
          TableRelation join = attemptMetaJoin(left, right);

          if (join != null)
          {
             return join;
          }

          Map<String, Integer> common = getCommonFields(left, right);
          if (common.isEmpty())
          {
             return null;
          }

          // Of the common fields, at least one must be part of a unique index.
          // If said index is multi-field, all fields in the index must
          // participate in the relation.
          Aast index1 = findJoiningIndex(left, common);
          Aast index2 = findJoiningIndex(right, common);

          if (index1 != null && index2 == null)
          {
             // The left table contains the primary key.
             Set<String> key = getIndexFieldNames(index1);
             join = new TableRelation(left, right, left, key, MANY_TO_ONE);
          }
          else if (index1 == null && index2 != null)
          {
             // The right table contains the primary key.
             Set<String> key = getIndexFieldNames(index2);
             join = new TableRelation(left, right, right, key, MANY_TO_ONE);
          }
          else if (index1 != null && index2 != null)
          {
             // In this case, both tables had a unique index containing one or
             // more common fields. Must analyze further...
             Set<String> set1 = getIndexFieldNames(index1);
             Set<String> set2 = getIndexFieldNames(index2);
             Set<String> commonKeys = common.keySet();
             commonKeys.retainAll(set1);
             commonKeys.retainAll(set2);
             Aast primary = null;
             boolean match1 = (set1.equals(commonKeys));
             boolean match2 = (set2.equals(commonKeys));
             int type = -1;
             if (match1 && !match2)
             {
                primary = left;
                type = MANY_TO_ONE;
             }
             else if (!match1 && match2)
             {
                primary = right;
                type = MANY_TO_ONE;
             }
             else if (match1 && match2)
             {
                type = ONE_TO_ONE;
             }
             else
             {
                // It is ambiguous which end represents the primary and which
                // the foreign end of this relation. Probably requires manual
                // inspection and a hint.
                String msg = "Cannot determine join type: " + join + System.lineSeparator() +
                   "   " + left.getText() + " matching index: " + set1 + System.lineSeparator() +
                   "   " + right.getText() + " matching index: " + set2;
                LOG.log(Level.SEVERE, msg);
             }

             if (type != -1 && !common.isEmpty())
             {
                join = new TableRelation(left, right, primary, commonKeys, type);
             }
          }

          return join;
       }

       /**
        * Attempt to determine a primary-foreign key join between two metadata tables.
        *
        * @param   left
        *          Table on the left side of the join.
        * @param   right
        *          Table on the right side of the join.
        *
        * @return  A <code>TableRelation</code> instance, if a join exists, else <code>null</code>.
        */
       private TableRelation attemptMetaJoin(Aast left, Aast right)
       {
          String leftName = left.getText().toLowerCase();
          String rightName = right.getText().toLowerCase();

          if (!metaTables.contains(leftName) || !metaTables.contains(rightName))
          {
             return null;
          }

          String fkField = null;
          int len1 = rightName.length();
          int len2 = "-recid".length();
          Iterator<Aast> iter = dictionary.fields(left);
          while (iter.hasNext())
          {
             Aast next = iter.next();
             if (next.getType() == FIELD_RECID)
             {
                String fieldName = next.getText().toLowerCase();
                int p1 = fieldName.indexOf(rightName);
                int p2 = fieldName.indexOf("-recid");
                if (p1 == 0 && p2 == len1 && fieldName.length() == (p2 + len2))
                {
                   fkField = next.getText().toLowerCase();
                   break;
                }
             }
          }

          MetaTableRelation join = null;

          if (fkField != null)
          {
             Set<String> key = new HashSet<String>();
             key.add(fkField);
             join = new MetaTableRelation(left, right, key);
          }

          return join;
       }

       /**
        * Compose a map of field names to field token types for the given table.
        * The keys (field names) are lowercased for uniformity. Iteration over
        * the key set will return field names in the order in which they were
        * added to the table AST.
        *
        * @param   table
        *          AST of the table to scan for fields when composing the map.
        *
        * @return  Map of field names to field token types.
        */
       private Map<String, Integer> getFieldMap(Aast table)
       {
          Map<String, Integer> map = new LinkedHashMap<String, Integer>();
          Iterator<Aast> iter = dictionary.fields(table);
          while (iter.hasNext())
          {
             Aast next = iter.next();
             map.put(next.getText().toLowerCase(), Integer.valueOf(next.getType()));
          }

          return map;
       }

       /**
        * Compose a map of field names to field token types which represents the
        * intersection of the fields (by name and token type) of the two tables
        * specified. These fields represent the possible, <em>natural</em> join
        * points between the two tables. Field names are compared without regard
        * to case when determining the intersection.
        *
        * @param   left
        *          The left-hand table of a two-table join.
        * @param   right
        *          The right-hand table of a two-table join.
        *
        * @return  The map of fields which are common between the two tables.
        */
       private Map<String, Integer> getCommonFields(Aast left, Aast right)
       {
          // Get the intersection of field names.
          Map<String, Integer> mapLeft = getFieldMap(left);
          Map<String, Integer> mapRight = getFieldMap(right);
          Set<String> set = mapLeft.keySet();
          set.retainAll(mapRight.keySet());

          // Check that each remaining field's type matches.
          Iterator<String> iter = set.iterator();
          while (iter.hasNext())
          {
             String next = iter.next();
             Integer type1 = mapLeft.get(next);
             Integer type2 = mapRight.get(next);
             if (!type1.equals(type2))
             {
                iter.remove();
             }
          }

          return mapLeft;
       }

       /**
        * Compose a set of the names of all fields defined for the given index.
        * Names are lowercased for uniformity.
        *
        * @param   index
        *          Index whose fields are to be included in the set.
        *
        * @return  Set of index field names.
        */
       private Set<String> getIndexFieldNames(Aast index)
       {
          Set<String> set = new LinkedHashSet<String>();
          String tableName = index.getParent().getText();
          Aast next = index.getImmediateChild(INDEX_FIELD, null);
          while (next != null)
          {
             set.add(next.getText().toLowerCase());
             next = index.getImmediateChild(INDEX_FIELD, next);
          }

          return set;
       }

       /**
        * Given a table AST and a map of fields which this table has in common
        * (by name and type) with another table, find the index which can be
        * used to join this table with the other. The index must be unique and
        * must contain only fields which are in the common map. There should
        * be only one such index in the table, but this restriction is not
        * enforced here; once a suitable index is found, it is returned.
        *
        * @param   table
        *          AST of table to be searched for a suitable index.
        * @param   common
        *          Map of field ASTs which the given table has in common with
        *          another table.
        *
        * @return  AST of the unique index (from the schema dictionary) which
        *          defines the join between this table and another, based upon
        *          fields described by <code>common</code>, or <code>null</code>
        *          if no such index is found.
        */
       private Aast findJoiningIndex(Aast table, Map<String, Integer> common)
       {
          Aast index = null;

          Iterator<Aast> iter = dictionary.indices(table);
          while (index == null && iter.hasNext())
          {
             Aast next = iter.next();

             boolean unique = false;
             Aast props = next.getImmediateChild(PROPERTIES, null);
             while (!unique && props != null)
             {
                unique = (props.getImmediateChild(KW_UNIQUE, null) != null);
                props = next.getImmediateChild(PROPERTIES, props);
             }
             if (!unique)
             {
                continue;
             }

             Aast field = next.getImmediateChild(INDEX_FIELD, null);
             boolean canJoin = (field != null);
             while (canJoin && field != null)
             {
                String name = field.getText().toLowerCase();
                field = next.getImmediateChild(INDEX_FIELD, field);
                canJoin = common.containsKey(name);
             }

             if (canJoin)
             {
                index = next;
             }
          }

          return index;
       }

       /**
        * Recursively create a tree which defines relation dependencies. The
        * root of the tree has no primary key dependencies. Each child node
        * has a foreign key dependency on its parent.
        *
        * @param   nodeMap
        *          Map of table ASTs to collections of table join objects.
        * @param   table
        *          The table which represents the current node in the tree
        *          being built.
        * @param   keyFields
        *          Set of field names which define the relation between this
        *          table and its parent.
        *
        * @return  A {@link RelationNode} object which represents the current
        *          table. Its parent is its dependency and its children are its
        *          dependents.
        */
       private RelationNode createTree(Map<Aast, Collection<TableRelation>> nodeMap,
                                       Aast table,
                                       Collection<String> keyFields)
       {
          RelationNode node = new RelationNode(table, keyFields);

          Collection<TableRelation> relations = nodeMap.get(table);
          if (relations != null)
          {
             Iterator<TableRelation> iter = relations.iterator();
             while (iter.hasNext())
             {
                TableRelation join = iter.next();
                Aast foreign = join.getRight();
                Collection<String> key = join.getKey();
                RelationNode child = createTree(nodeMap, foreign, key);
                node.addChild(child);
             }
          }

          return node;
       }

       /**
        * Test driver which analyzes all potential, natural relations between
        * every possible pair of tables in a given database. The (possibly
        * very large) tree is dumped to the console.
        *
        * @param   args
        *          Command line arguments. One argument is expected: the logical
        *          name of the database to analyze.
        */
       public static void main(String[] args)
       {
          try
          {
             String database = args[0];
             SchemaDictionary dictionary = new SchemaDictionary(database);
             RelationAnalyzer analyzer = new RelationAnalyzer(dictionary);
             Set<TableRelation> set = analyzer.getAllRelations(database);

             List<RelationNode> roots = analyzer.analyze(set);
             Iterator<RelationNode> iter = roots.iterator();
             while (iter.hasNext())
             {
                analyzer.dumpTree(iter.next());
             }
          }
          catch (Exception exc)
          {
             LOG.log(Level.SEVERE, "", exc);
          }
       }
    }