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.sql.validate;
  
  import org.apache.calcite.rel.type.RelDataType;
  import org.apache.calcite.rel.type.RelDataTypeField;
  import org.apache.calcite.rel.type.StructKind;
  import org.apache.calcite.sql.SqlCall;
  import org.apache.calcite.sql.SqlIdentifier;
  import org.apache.calcite.sql.SqlNode;
  import org.apache.calcite.sql.SqlNodeList;
  import org.apache.calcite.sql.SqlSelect;
  import org.apache.calcite.sql.SqlWindow;
  import org.apache.calcite.util.Pair;
  import org.apache.calcite.util.Util;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.Iterables;
  
  import org.checkerframework.checker.nullness.qual.Nullable;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.List;
  import java.util.Map;
  
  import static java.util.Objects.requireNonNull;
  
  /**
   * Name-resolution scope. Represents any position in a parse tree than an
   * expression can be, or anything in the parse tree which has columns.
   *
   * <p>When validating an expression, say "foo"."bar", you first use the
   * {@link #resolve} method of the scope where the expression is defined to
   * locate "foo". If successful, this returns a
   * {@link SqlValidatorNamespace namespace} describing the type of the resulting
   * object.
   */
  public interface SqlValidatorScope {
    //~ Methods ----------------------------------------------------------------
  
    /**
     * Returns the validator which created this scope.
     */
    SqlValidator getValidator();
  
    /**
     * Returns the root node of this scope. Never null.
     */
    SqlNode getNode();
  
    /**
     * Looks up a node with a given name. Adds the match(es) to the resolved if found.
     *
     * @param names       Name of node to find, maybe partially or fully qualified
     * @param nameMatcher Name matcher
     * @param deep        Whether to look more than one level deep
     * @param resolved    Callback wherein to write the match(es) we find
     */
    void resolve(List<String> names, SqlNameMatcher nameMatcher, boolean deep,
        Resolved resolved);
  
    // CHECKSTYLE: IGNORE 1
    /** @deprecated Use
     * {@link #findQualifyingTableNames(String, SqlNode, SqlNameMatcher)} */
    @Deprecated // to be removed before 2.0
    Pair<String, SqlValidatorNamespace> findQualifyingTableName(String columnName,
        SqlNode ctx);
  
    /**
     * Finds all table aliases which are implicitly qualifying an unqualified
     * column name.
     *
     * <p>This method is only implemented in scopes (such as
     * {@link org.apache.calcite.sql.validate.SelectScope}) which can be the
     * context for name-resolution. In scopes such as
     * {@link org.apache.calcite.sql.validate.IdentifierNamespace}, it throws
     * {@link UnsupportedOperationException}.
     *
     * @param columnName Column name
     * @param ctx        Validation context, to appear in any error thrown
     * @param nameMatcher Name matcher
     *
     * @return Map of applicable table alias and namespaces, never null, empty
     * if no aliases found
     */
    Map<String, ScopeChild> findQualifyingTableNames(String columnName,
        SqlNode ctx, SqlNameMatcher nameMatcher);
  
    /**
     * Collects the {@link SqlMoniker}s of all possible columns in this scope.
     *
     * @param result an array list of strings to add the result to
     */
    void findAllColumnNames(List<SqlMoniker> result);
  
    /**
     * Collects the {@link SqlMoniker}s of all table aliases (uses of tables in
     * query FROM clauses) available in this scope.
     *
     * @param result a list of monikers to add the result to
     */
    void findAliases(Collection<SqlMoniker> result);
  
    /**
     * Converts an identifier into a fully-qualified identifier. For example,
     * the "empno" in "select empno from emp natural join dept" becomes
     * "emp.empno".
     *
     * @return A qualified identifier, never null
     */
    SqlQualified fullyQualify(SqlIdentifier identifier);
  
    /** Returns whether an expression is a reference to a measure column. */
    default boolean isMeasureRef(SqlNode node) {
      if (node instanceof SqlIdentifier) {
        final SqlQualified q = fullyQualify((SqlIdentifier) node);
        if (q.suffix().size() == 1
            && q.namespace != null) {
          final @Nullable RelDataTypeField f =
              q.namespace.field(q.suffix().get(0));
          if (q.namespace instanceof SelectNamespace) {
            final SqlSelect select = ((SelectNamespace) q.namespace).getNode();
            return f != null
                && SqlValidatorUtil.isMeasure(select.getSelectList().get(f.getIndex()));
          }
          return f != null
              && f.getType().isMeasure();
        }
      }
      return false;
    }
  
    /**
     * Registers a relation in this scope.
     *
     * @param ns    Namespace representing the result-columns of the relation
     * @param alias Alias with which to reference the relation, must not be null
     * @param nullable Whether this is a null-generating side of a join
     */
    void addChild(SqlValidatorNamespace ns, String alias, boolean nullable);
  
    /**
     * Finds a window with a given name. Returns null if not found.
     */
    @Nullable SqlWindow lookupWindow(String name);
  
    /**
     * Returns whether an expression is monotonic in this scope. For example, if
     * the scope has previously been sorted by columns X, Y, then X is monotonic
     * in this scope, but Y is not.
     */
    SqlMonotonicity getMonotonicity(SqlNode expr);
  
    /**
     * Returns the expressions by which the rows in this scope are sorted. If
     * the rows are unsorted, returns null.
     */
    @Nullable SqlNodeList getOrderList();
  
    /**
     * Resolves a single identifier to a column, and returns the datatype of
     * that column.
     *
     * <p>If it cannot find the column, returns null. If the column is
     * ambiguous, throws an error with context <code>ctx</code>.
     *
     * @param name Name of column
     * @param ctx  Context for exception
     * @return Type of column, if found and unambiguous; null if not found
     */
    @Nullable RelDataType resolveColumn(String name, SqlNode ctx);
  
    /**
     * Returns the scope within which operands to a call are to be validated.
     * Usually it is this scope, but when the call is to an aggregate function
     * and this is an aggregating scope, it will be a a different scope.
     *
     * @param call Call
     * @return Scope within which to validate arguments to call.
     */
    SqlValidatorScope getOperandScope(SqlCall call);
  
    /**
     * Performs any scope-specific validation of an expression. For example, an
     * aggregating scope requires that expressions are valid aggregations. The
     * expression has already been validated.
     */
    void validateExpr(SqlNode expr);
  
    // CHECKSTYLE: IGNORE 1
    /** @deprecated Use
     * {@link #resolveTable(List, SqlNameMatcher, Path, Resolved)}. */
    @Deprecated // to be removed before 2.0
    @Nullable SqlValidatorNamespace getTableNamespace(List<String> names);
  
    /**
     * Looks up a table in this scope from its name. If found, calls
     * {@link Resolved#resolve(List, SqlNameMatcher, boolean, Resolved)}.
     * {@link TableNamespace} that wraps it. If the "table" is defined in a
     * {@code WITH} clause it may be a query, not a table after all.
     *
     * <p>The name matcher is not null, and one typically uses
     * {@link SqlValidatorCatalogReader#nameMatcher()}.
     *
     * @param names Name of table, may be qualified or fully-qualified
     * @param nameMatcher Name matcher
     * @param path List of names that we have traversed through so far
     */
    void resolveTable(List<String> names, SqlNameMatcher nameMatcher, Path path,
        Resolved resolved);
  
    /** Converts the type of an expression to nullable, if the context
     * warrants it. */
    RelDataType nullifyType(SqlNode node, RelDataType type);
  
    /** Returns whether this scope is enclosed within {@code scope2} in such
     * a way that it can see the contents of {@code scope2}. */
    default boolean isWithin(SqlValidatorScope scope2)  {
      return this == scope2;
    }
  
    /** Callback from {@link SqlValidatorScope#resolve}. */
    interface Resolved {
      void found(SqlValidatorNamespace namespace, boolean nullable,
          SqlValidatorScope scope, Path path, List<String> remainingNames);
      int count();
    }
  
    /** A sequence of steps by which an identifier was resolved. Immutable. */
    abstract class Path {
      /** The empty path. */
      @SuppressWarnings("StaticInitializerReferencesSubClass")
      public static final EmptyPath EMPTY = new EmptyPath();
  
      /** Creates a path that consists of this path plus one additional step. */
      public Step plus(@Nullable RelDataType rowType, int i, String name, StructKind kind) {
        return new Step(this, rowType, i, name, kind);
      }
  
      /** Number of steps in this path. */
      public int stepCount() {
        return 0;
      }
  
      /** Returns the steps in this path. */
      public List<Step> steps() {
        ImmutableList.Builder<Step> paths = new ImmutableList.Builder<>();
        build(paths);
        return paths.build();
      }
  
      /** Returns a list ["step1", "step2"]. */
      List<String> stepNames() {
        return Util.transform(steps(), input -> input.name);
      }
  
      protected void build(ImmutableList.Builder<Step> paths) {
      }
  
      @Override public String toString() {
        return stepNames().toString();
      }
    }
  
    /** A path that has no steps. */
    class EmptyPath extends Path {
    }
  
    /** A step in resolving an identifier. */
    class Step extends Path {
      final Path parent;
      final @Nullable RelDataType rowType;
      public final int i;
      public final String name;
      final StructKind kind;
  
      Step(Path parent, @Nullable RelDataType rowType, int i, String name,
          StructKind kind) {
        this.parent = requireNonNull(parent, "parent");
        this.rowType = rowType; // may be null
        this.i = i;
        this.name = name;
        this.kind = requireNonNull(kind, "kind");
      }
  
      @Override public int stepCount() {
        return 1 + parent.stepCount();
      }
  
      @Override protected void build(ImmutableList.Builder<Step> paths) {
        parent.build(paths);
        paths.add(this);
      }
    }
  
    /** Default implementation of
     * {@link org.apache.calcite.sql.validate.SqlValidatorScope.Resolved}. */
    class ResolvedImpl implements Resolved {
      final List<Resolve> resolves = new ArrayList<>();
  
      @Override public void found(SqlValidatorNamespace namespace,
          boolean nullable, SqlValidatorScope scope, Path path,
          List<String> remainingNames) {
        if (scope instanceof TableScope) {
          scope = scope.getValidator().getSelectScope((SqlSelect) scope.getNode());
        }
        if (scope instanceof AggregatingSelectScope) {
          scope = ((AggregatingSelectScope) scope).parent;
          assert scope instanceof SelectScope;
        }
        resolves.add(
            new Resolve(namespace, nullable, scope, path, remainingNames));
      }
  
      @Override public int count() {
        return resolves.size();
      }
  
      public Resolve only() {
        return Iterables.getOnlyElement(resolves);
      }
  
      /** Resets all state. */
      public void clear() {
        resolves.clear();
      }
  
    }
  
    /** A match found when looking up a name. */
    class Resolve {
      public final SqlValidatorNamespace namespace;
      private final boolean nullable;
      public final SqlValidatorScope scope;
      public final Path path;
      /** Names not matched; empty if it was a full match. */
      final List<String> remainingNames;
  
      Resolve(SqlValidatorNamespace namespace, boolean nullable,
          SqlValidatorScope scope, Path path, List<String> remainingNames) {
        this.namespace = requireNonNull(namespace, "namespace");
        this.nullable = nullable;
        this.scope = scope;
        assert !(scope instanceof TableScope);
        this.path = requireNonNull(path, "path");
        this.remainingNames = ImmutableList.copyOf(remainingNames);
      }
  
      /** The row type of the found namespace, nullable if the lookup has
       * looked into outer joins. */
      public RelDataType rowType() {
        return namespace.getValidator().getTypeFactory()
            .createTypeWithNullability(namespace.getRowType(), nullable);
      }
    }
  }
  