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.plan.volcano;
  
  import org.apache.calcite.rel.RelNode;
  import org.apache.calcite.rel.rules.SubstitutionRule;
  import org.apache.calcite.util.trace.CalciteTrace;
  
  import com.google.common.collect.HashMultimap;
  import com.google.common.collect.Multimap;
  
  import org.checkerframework.checker.nullness.qual.Nullable;
  import org.slf4j.Logger;
  
  import java.io.PrintWriter;
  import java.io.StringWriter;
  import java.util.ArrayDeque;
  import java.util.HashSet;
  import java.util.Queue;
  import java.util.Set;
  
  import static java.util.Objects.requireNonNull;
  
  /**
   * Priority queue of relexps whose rules have not been called, and rule-matches
   * which have not yet been acted upon.
   */
  class IterativeRuleQueue extends RuleQueue {
    //~ Static fields/initializers ---------------------------------------------
  
    private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
  
    //~ Instance fields --------------------------------------------------------
  
    /**
     * The list of rule-matches. Initially, there is an empty {@link MatchList}.
     * As the planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match
     * is added to the appropriate MatchList(s). As the planner completes the
     * match, the matching entry is removed from this list to avoid unused work.
     */
    final MatchList matchList = new MatchList();
  
    //~ Constructors -----------------------------------------------------------
  
    IterativeRuleQueue(VolcanoPlanner planner) {
      super(planner);
    }
  
    //~ Methods ----------------------------------------------------------------
    /**
     * Clear internal data structure for this rule queue.
     */
    @Override public boolean clear() {
      boolean empty = true;
      if (!matchList.queue.isEmpty() || !matchList.preQueue.isEmpty()) {
        empty = false;
      }
      matchList.clear();
      return !empty;
    }
  
    /**
     * Add a rule match.
     */
    @Override public void addMatch(VolcanoRuleMatch match) {
      final String matchName = match.toString();
  
      if (!matchList.names.add(matchName)) {
        // Identical match has already been added.
        return;
      }
  
      LOGGER.trace("Rule-match queued: {}", matchName);
  
      matchList.offer(match);
  
      matchList.matchMap.put(
          requireNonNull(planner.getSubset(match.rels[0])), match);
    }
  
    /**
     * Removes the rule match from the head of match list, and returns it.
     *
     * <p>Returns {@code null} if there are no more matches.
     *
     * <p>Note that the VolcanoPlanner may still decide to reject rule matches
     * which have become invalid, say if one of their operands belongs to an
     * obsolete set or has been pruned.
     *
     */
    public @Nullable VolcanoRuleMatch popMatch() {
      dumpPlannerState();
  
      VolcanoRuleMatch match;
      for (;;) {
        if (matchList.size() == 0) {
          return null;
        }
  
        dumpRuleQueue(matchList);
  
        match = matchList.poll();
        if (match == null) {
          return null;
        }
  
        if (skipMatch(match)) {
          LOGGER.debug("Skip match: {}", match);
        } else {
          break;
        }
      }
  
      // If sets have merged since the rule match was enqueued, the match
      // may not be removed from the matchMap because the subset may have
      // changed, it is OK to leave it since the matchMap will be cleared
      // at the end.
      matchList.matchMap.remove(
          planner.getSubset(match.rels[0]), match);
  
      LOGGER.debug("Pop match: {}", match);
      return match;
    }
  
    /**
     * Dumps rules queue to the logger when debug level is set to {@code TRACE}.
     */
    private static void dumpRuleQueue(MatchList matchList) {
      if (LOGGER.isTraceEnabled()) {
        StringBuilder b = new StringBuilder();
        b.append("Rule queue:");
        for (VolcanoRuleMatch rule : matchList.preQueue) {
          b.append("\n");
          b.append(rule);
        }
        for (VolcanoRuleMatch rule : matchList.queue) {
          b.append("\n");
          b.append(rule);
        }
        LOGGER.trace(b.toString());
      }
    }
  
    /**
     * Dumps planner's state to the logger when debug level is set to {@code TRACE}.
     */
    private void dumpPlannerState() {
      if (LOGGER.isTraceEnabled()) {
        StringWriter sw = new StringWriter();
        PrintWriter pw = new PrintWriter(sw);
        planner.dump(pw);
        pw.flush();
        LOGGER.trace(sw.toString());
        RelNode root = planner.getRoot();
        if (root != null) {
          root.getCluster().invalidateMetadataQuery();
        }
      }
    }
  
    //~ Inner Classes ----------------------------------------------------------
  
    /**
     * MatchList represents a set of {@link VolcanoRuleMatch rule-matches}.
     */
    private static class MatchList {
  
      /**
       * Rule match queue for SubstitutionRule.
       */
      private final Queue<VolcanoRuleMatch> preQueue = new ArrayDeque<>();
  
      /**
       * Current list of VolcanoRuleMatches for this phase. New rule-matches
       * are appended to the end of this queue.
       * The rules are not sorted in any way.
       */
      private final Queue<VolcanoRuleMatch> queue = new ArrayDeque<>();
  
      /**
       * A set of rule-match names contained in {@link #queue}. Allows fast
       * detection of duplicate rule-matches.
       */
      final Set<String> names = new HashSet<>();
  
      /**
       * Multi-map of RelSubset to VolcanoRuleMatches.
       */
      final Multimap<RelSubset, VolcanoRuleMatch> matchMap =
          HashMultimap.create();
  
      int size() {
        return preQueue.size() + queue.size();
      }
  
      @Nullable VolcanoRuleMatch poll() {
        VolcanoRuleMatch match = preQueue.poll();
        if (match == null) {
          match = queue.poll();
        }
        return match;
      }
  
      void offer(VolcanoRuleMatch match) {
        if (match.getRule() instanceof SubstitutionRule) {
          preQueue.offer(match);
        } else {
          queue.offer(match);
        }
      }
  
      void clear() {
        preQueue.clear();
        queue.clear();
        names.clear();
        matchMap.clear();
      }
    }
  }
  