content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.calcite.rel.rules;
  
  import org.apache.calcite.rel.core.JoinRelType;
  
  import com.google.common.collect.ImmutableMap;
  
  import java.util.ArrayList;
  import java.util.List;
  
  /**
   * Conflict detection algorithm based on CD-C. More details are in paper:
   * <a href="https://dl.acm.org/doi/pdf/10.1145/2463676.2465314">
   *   On the correct and complete enumeration of the core search space</a>.
   */
  public class ConflictDetectionHelper {
  
    private ConflictDetectionHelper() {
    }
  
    /**
     * Tables in the paper involve 7 types of join: cross product, inner join, semi join, anti join,
     * left join, full join, group join. Cross product and inner join have the same result in the
     * associative/left_asscom/right_asscom tables. The inner join with true condition is equivalent
     * to the cross product, and there is no group join in Calcite, so cross product and group join
     * do not appear in the following table.
     */
    private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE =
        ImmutableMap.<JoinRelType, Integer>builder()
            .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2)
            .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build();
  
    /**
     * For {@code e1 joinA e2 joinB e3}, whether joinA and joinB are associative is shown in the
     * following table. In particular, for left/full-A and left-B, we assume that the predicates of
     * left-B are not null-rejecting on e2; for full-A and full-B, we assume that the predicates of
     * full-A and full-B are not null-rejecting on e2. See table.2 in paper.
     */
    private static final boolean[][] ASSOCIATIVE_TABLE = {
        //            inner-B  semi-B  anti-B  left-B  full-B
        /* inner-A */ {true,   true,   true,   true,   false},
        /* semi-A  */ {false,  false,  false,  false,  false},
        /* anti-A  */ {false,  false,  false,  false,  false},
        /* left-A  */ {false,  false,  false,  false,  false},
        /* full-A  */ {false,  false,  false,  false,  false}};
  
    /**
     * For {@code e1 joinA e2 joinB e3}, whether joinA and joinB are left asscom is shown in the
     * following table. In particular, for left-A and full-B, we assume that the predicates of left-A
     * are not null-rejecting on e1; for full-A and left-B, we assume that the predicates of left-B
     * are not null-rejecting on e3; for full-A and full-B, we assume that the predicates of full-A
     * and full-B are not null-rejecting on e1. See table.3 in paper.
     */
    private static final boolean[][] LEFT_ASSCOM_TABLE = {
        //            inner-B  semi-B  anti-B  left-B  full-B
        /* inner-A */ {true,   true,   true,   true,   false},
        /* semi-A  */ {true,   true,   true,   true,   false},
        /* anti-A  */ {true,   true,   true,   true,   false},
        /* left-A  */ {true,   true,   true,   true,   false},
        /* full-A  */ {false,  false,  false,  false,  false}};
  
    /**
     * For {@code e1 joinA e2 joinB e3}, whether joinA and joinB are right asscom is shown in the
     * following table. In particular, for full-A and full-B, we assume that the predicates of full-A
     * and full-B are not null-rejecting on e3. See table.3 in paper.
     */
    private static final boolean[][] RIGHT_ASSCOM_TABLE = {
        //            inner-B  semi-B  anti-B  left-B  full-B
        /* inner-A */ {true,   false,  false,  false,  false},
        /* semi-A  */ {false,  false,  false,  false,  false},
        /* anti-A  */ {false,  false,  false,  false,  false},
        /* left-A  */ {false,  false,  false,  false,  false},
        /* full-A  */ {false,  false,  false,  false,  false}};
  
    /**
     * Make conflict rules for join operator based on CD-C. See Figure.11 in paper.
     *
     * @param leftSubEdges  left sub operators
     * @param rightSubEdges right sub operators
     * @param joinType      current join operator
     * @return  conflict rule list
     */
    public static List<ConflictRule> makeConflictRules(
        List<HyperEdge> leftSubEdges,
        List<HyperEdge> rightSubEdges,
        JoinRelType joinType) {
      List<ConflictRule> conflictRules = new ArrayList<>();
      //       o_b
      //      /   \
      //    ...   ...
      //    /
      //  o_a
      //
      // calculate the conflict rules for join_operator_b based on the all join operator
      // (join_operator_a) on the left side of join_operator_b
      for (HyperEdge leftSubEdge : leftSubEdges) {
        if (!isAssociative(leftSubEdge.getJoinType(), joinType)) {
          // if (o_a, o_b) does not satisfy the associative law
          if (leftSubEdge.getLeftNodeUsedInPredicate() != 0) {
            // if the predicate of o_a does not reference the table on its left side,
            // a less restrictive conflict rule will be added
            conflictRules.add(
                new ConflictRule(
                    leftSubEdge.getInitialRightNodeBits(),
                    leftSubEdge.getLeftNodeUsedInPredicate()));
          } else {
            conflictRules.add(
                new ConflictRule(
                leftSubEdge.getInitialRightNodeBits(),
                leftSubEdge.getInitialLeftNodeBits()));
          }
        }
        if (!isLeftAsscom(leftSubEdge.getJoinType(), joinType)) {
          // if (o_a, o_b) does not satisfy the left-asscom law
          if (leftSubEdge.getRightNodeUsedInPredicate() != 0) {
            // if the predicate of o_a does not reference the table on its right side,
            // a less restrictive conflict rule will be added
            conflictRules.add(
                new ConflictRule(
                    leftSubEdge.getInitialLeftNodeBits(),
                    leftSubEdge.getRightNodeUsedInPredicate()));
          } else {
            conflictRules.add(
                new ConflictRule(
                    leftSubEdge.getInitialLeftNodeBits(),
                    leftSubEdge.getInitialRightNodeBits()));
          }
        }
      }
  
      //       o_b
      //      /   \
      //    ...   ...
      //            \
      //            o_a
      //
      // calculate the conflict rules for join_operator_b based on the all join operator
      // (join_operator_a) on the right side of join_operator_b
      for (HyperEdge rightSubEdge : rightSubEdges) {
        if (!isAssociative(joinType, rightSubEdge.getJoinType())) {
          // if (o_b, o_a) does not satisfy the associative law
          if (rightSubEdge.getRightNodeUsedInPredicate() != 0) {
            // if the predicate of o_a does not reference the table on its right side,
            // a less restrictive conflict rule will be added
            conflictRules.add(
                new ConflictRule(
                    rightSubEdge.getInitialLeftNodeBits(),
                    rightSubEdge.getRightNodeUsedInPredicate()));
          } else {
            conflictRules.add(
                new ConflictRule(
                    rightSubEdge.getInitialLeftNodeBits(),
                    rightSubEdge.getInitialRightNodeBits()));
          }
        }
        if (!isRightAsscom(joinType, rightSubEdge.getJoinType())) {
          // if (o_b, o_a) does not satisfy the right-asscom law
          if (rightSubEdge.getLeftNodeUsedInPredicate() != 0) {
            // if the predicate of o_a does not reference the table on its left side,
            // a less restrictive conflict rule will be added
            conflictRules.add(
                new ConflictRule(
                    rightSubEdge.getInitialRightNodeBits(),
                    rightSubEdge.getLeftNodeUsedInPredicate()));
          } else {
            conflictRules.add(
                new ConflictRule(
                    rightSubEdge.getInitialRightNodeBits(),
                    rightSubEdge.getInitialLeftNodeBits()));
          }
        }
      }
      return conflictRules;
    }
  
    public static boolean isCommutative(JoinRelType operator) {
      return operator == JoinRelType.INNER || operator == JoinRelType.FULL;
    }
  
    public static boolean isAssociative(JoinRelType operatorA, JoinRelType operatorB) {
      Integer indexA = INDEX_OF_TABLE.get(operatorA);
      Integer indexB = INDEX_OF_TABLE.get(operatorB);
      if (indexA == null || indexB == null) {
        return false;
      }
      return ASSOCIATIVE_TABLE[indexA][indexB];
    }
  
    public static boolean isLeftAsscom(JoinRelType operatorA, JoinRelType operatorB) {
      Integer indexA = INDEX_OF_TABLE.get(operatorA);
      Integer indexB = INDEX_OF_TABLE.get(operatorB);
      if (indexA == null || indexB == null) {
        return false;
      }
      return LEFT_ASSCOM_TABLE[indexA][indexB];
    }
  
    public static boolean isRightAsscom(JoinRelType operatorA, JoinRelType operatorB) {
      Integer indexA = INDEX_OF_TABLE.get(operatorA);
      Integer indexB = INDEX_OF_TABLE.get(operatorB);
      if (indexA == null || indexB == null) {
        return false;
      }
      return RIGHT_ASSCOM_TABLE[indexA][indexB];
    }
  
  }
  