private void matchRecurse()

in core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java [270:413]
118 lines of code
27 McCabe index (conditional complexity)

  private void matchRecurse(int solve) {
    assert solve > 0;
    assert solve <= rule.operands.size();
    final List<RelOptRuleOperand> operands = getRule().operands;
    if (solve == operands.size()) {
      // We have matched all operands. Now ask the rule whether it
      // matches; this gives the rule chance to apply side-conditions.
      // If the side-conditions are satisfied, we have a match.
      if (getRule().matches(this)) {
        onMatch();
      }
    } else {
      final int[] solveOrder = castNonNull(operand0.solveOrder);
      final int operandOrdinal = solveOrder[solve];
      final int previousOperandOrdinal = solveOrder[solve - 1];
      boolean ascending = operandOrdinal < previousOperandOrdinal;
      final RelOptRuleOperand previousOperand =
          operands.get(previousOperandOrdinal);
      final RelOptRuleOperand operand = operands.get(operandOrdinal);
      final RelNode previous = rels[previousOperandOrdinal];

      final RelOptRuleOperand parentOperand;
      final Collection<? extends RelNode> successors;
      if (ascending) {
        assert previousOperand.getParent() == operand;
        assert operand.getMatchedClass() != RelSubset.class;
        if (previousOperand.getMatchedClass() != RelSubset.class
            && previous instanceof RelSubset) {
          throw new RuntimeException("RelSubset should not match with "
              + previousOperand.getMatchedClass().getSimpleName());
        }
        parentOperand = operand;
        final RelSubset subset = volcanoPlanner.getSubsetNonNull(previous);
        successors = subset.getParentRels();
      } else {
        parentOperand =
            requireNonNull(operand.getParent(),
                () -> "operand.getParent() for " + operand);
        final RelNode parentRel = rels[parentOperand.ordinalInRule];
        final List<RelNode> inputs = parentRel.getInputs();
        // if the child is unordered, then add all rels in all input subsets to the successors list
        // because unordered can match child in any ordinal
        if (parentOperand.childPolicy == RelOptRuleOperandChildPolicy.UNORDERED) {
          if (operand.getMatchedClass() == RelSubset.class) {
            // Find all the sibling subsets that satisfy this subset's traitSet
            successors = inputs.stream()
              .flatMap(subset -> ((RelSubset) subset).getSubsetsSatisfyingThis())
              .collect(Collectors.toList());
          } else {
            List<RelNode> allRelsInAllSubsets = new ArrayList<>();
            Set<RelNode> duplicates = new HashSet<>();
            for (RelNode input : inputs) {
              if (!duplicates.add(input)) {
                // Ignore duplicate subsets
                continue;
              }
              RelSubset inputSubset = (RelSubset) input;
              for (RelNode rel : inputSubset.getRels()) {
                if (!duplicates.add(rel)) {
                  // Ignore duplicate relations
                  continue;
                }
                allRelsInAllSubsets.add(rel);
              }
            }
            successors = allRelsInAllSubsets;
          }
        } else if (operand.ordinalInParent < inputs.size()) {
          // child policy is not unordered
          // we need to find the exact input node based on child operand's ordinalInParent
          final RelSubset subset =
              (RelSubset) inputs.get(operand.ordinalInParent);
          if (operand.getMatchedClass() == RelSubset.class) {
            // Find all the sibling subsets that satisfy this subset'straitSet
            successors =
              subset.getSubsetsSatisfyingThis().collect(Collectors.toList());
          } else {
            successors = subset.getRelList();
          }
        } else {
          // The operand expects parentRel to have a certain number
          // of inputs and it does not.
          successors = ImmutableList.of();
        }
      }

      for (RelNode rel : successors) {
        if (operand.getRule() instanceof TransformationRule
            && rel.getConvention() != previous.getConvention()) {
          continue;
        }
        if (!operand.matches(rel)) {
          continue;
        }
        if (ascending && operand.childPolicy != RelOptRuleOperandChildPolicy.UNORDERED) {
          // We know that the previous operand was *a* child of its parent,
          // but now check that it is the *correct* child.
          if (previousOperand.ordinalInParent >= rel.getInputs().size()) {
            continue;
          }
          final RelSubset input =
              (RelSubset) rel.getInput(previousOperand.ordinalInParent);
          if (previousOperand.getMatchedClass() == RelSubset.class) {
            // The matched subset (previous) should satisfy our input subset (input)
            if (input.getSubsetsSatisfyingThis().noneMatch(previous::equals)) {
              continue;
            }
          } else {
            if (!input.contains(previous)) {
              continue;
            }
          }
        }

        // Assign "childRels" if the operand is UNORDERED.
        switch (parentOperand.childPolicy) {
        case UNORDERED:
          // Note: below is ill-defined. Suppose there's a union with 3 inputs,
          // and the rule is written as Union.class, unordered(...)
          // What should be provided for the rest 2 arguments?
          // RelSubsets? Random relations from those subsets?
          // For now, Calcite code does not use getChildRels, so the bug is just waiting its day
          if (ascending) {
            final List<RelNode> inputs = Lists.newArrayList(rel.getInputs());
            inputs.set(previousOperand.ordinalInParent, previous);
            setChildRels(rel, inputs);
          } else {
            List<RelNode> inputs = getChildRels(previous);
            if (inputs == null) {
              inputs = Lists.newArrayList(previous.getInputs());
            }
            inputs.set(operand.ordinalInParent, rel);
            setChildRels(previous, inputs);
          }
          break;
        default:
          break;
        }

        rels[operandOrdinal] = rel;
        matchRecurse(solve + 1);
      }
    }
  }