Repository: sqlfluff/sqlfluff
Pull request: L025 should look at subqueries
<!--Firstly, thanks for adding this feature! Secondly, please check the key steps against the checklist below to make your contribution easy to merge.-->

<!--Please give the Pull Request a meaningful title (including the dialect this PR is for if it is dialect specific), as this will automatically be added to the release notes, and then the Change Log.-->

### Brief summary of the change made

Fixes #1462

This is basically a rewrite of `L025`. Previously, it inherited from `L020`. Now, its implementation largely relies on `SelectCrawler`. A couple of other rules needlessly inherited from `L025` that could've simply inherited from `L020` -- I updated those, because after the rewrite, inheriting from `L025` no longer worked.


### Pull Request checklist
- [x] Please confirm you have completed any of the necessary steps below.

- Included test cases to demonstrate any code changes, which may be one or more of the following:
  - `.yml` rule test cases in `test/fixtures/rules/std_rule_cases`.
  - `.sql`/`.yml` parser test cases in `test/fixtures/dialects` (note YML files can be auto generated with `tox -e generate-fixture-yml`).
  - Full autofix test cases in `test/fixtures/linter/autofix`.
  - Other.
- Added appropriate documentation for the change.
- Created GitHub issues for any relevant followup/future enhancements if appropriate.


Problem statement:
L025 removes alias which is used in subquery
_If this is a parsing or linting issue, please include a minimal SQL example which reproduces the issue, along with the `sqlfluff parse` output, `sqlfluff lint` output and `sqlfluff fix` output when relevant._

## Expected Behaviour
With fixing ~L031~ L025 the alias should replaced correctly also in subqueries.

## Observed Behaviour
A alias from the parent query is used in a subquery. After fixing the file, the alias of the parent was removed while the alias within the subquery remains.

## Steps to Reproduce
Fix this script:
```
WITH base AS (
    SELECT
        nvl(col1, col2) AS col1,
        col2,
        col3,
        col4,
        col5
    FROM
        SRC_PRD.MDM_EXTRACT
),
without_dup AS (
    SELECT
        DISTINCT col1,
        col2,
        col3,
        col4
    FROM
        base
)
SELECT
    col1,
    col2,
    col3,
    col4,
    (
        SELECT
            count(*)
        FROM
            base b
        WHERE
            a.col2 = b.col2
            AND b.col5 = 'X'
    ) AS X_CNT,
    (
        SELECT
            count(*)
        FROM
            base b
        WHERE
            a.col2 = b.col2
            AND b.col5 = 'Y'
    ) AS Y_CNT,
    (
        SELECT
            count(*)
        FROM
            base b
        WHERE
            a.col2 = b.col2
            AND b.col5 = 'Z'
    ) AS Z_CNT,
FROM
    without_dup a;
```

Alias `a` from `without_dup` is removed but lives in the where clause of the subselects.

## Dialect
exasol

## Version
Include the output of `sqlfluff --version` along with your Python version
sqlfluff, version 0.6.6
Python 3.8.12
## Configuration
default

Hints from issue discussion:
I believe this is actually rule L025 not L031 which is causing the issue.

Minimal reproducible test case:

```sql
SELECT
    col1,
    (
        SELECT
            count(*)
        FROM
            base b
        WHERE
            a.col2 = b.col2
    )
FROM
    without_dup a;
```

And then run:
```
sqlfluff fix -f test.sql --rules L025 --fixed-suffix FIXED
diff test.sql testFIXED.sql
```
> I believe this is actually rule L025 not L031 which is causing the issue.

I'm not sure - yet - how it all works, but isn't that because of both these rules?
![image](https://user-images.githubusercontent.com/10441317/136008463-47930169-52e9-477e-9e36-5eab1748316d.png)

The issue is reproducable with the following Subselect as well:
```
select
  COL_A
  , COL_B
from INSERTS INS
where COL_B != (select max(COL_B) from INSERTS X where INS.COL_A = X.COL_A)
```

![grafik](https://user-images.githubusercontent.com/93246302/139015722-6bd6545b-cfb8-4960-bd42-c783f4832b60.png)

After running the fix, the SQL is now broken:

![grafik](https://user-images.githubusercontent.com/93246302/139015785-86ac437d-1dbd-48ca-8168-a7493903fe5f.png)


Quick note: There is a class `SelectCrawler` in `sqlfluff.core.rules.analysis.select_crawler` used by a couple of existing rules. It recursively walks through the queries and subqueries in a file. It could be useful for fixing this bug.
Here's a twist:
```
select 
    col_1, 
    col_2
from values(1, 2) as t(col_1, col_2)
```

```
root@eca08d9e0fd0:/dbt# sqlfluff fix test_fix.sql || echo exit $?
==== finding fixable violations ====
== [test_fix.sql] FAIL                                                                                                                                                          
L:   4 | P:  22 | L025 | Alias 't' is never used in SELECT statement.
==== fixing violations ====
1 fixable linting violations found
Are you sure you wish to attempt to fix these? [Y/n] ...
Attempting fixes...
Persisting Changes...
== [test_fix.sql] PASS
Done. Please check your files to confirm.
All Finished 📜 🎉!
```

```
select
    col_1,
    col_2
from values(1, 2)
```

dialect spark3
sqlfluff, version 0.9.0
Python 3.8.12

It correctly realizes that table alias `t` is unused, then the fix removes the column aliases as well, which are used. 

Is this actually a separate issue? 
@mcannamela: That looks like a separate issue, because this one is talking about nested `SELECT` queries.
thanks, i'll raise it as such
Detailed design for a fix.
```
@dataclass
class AliasUsage:
    aliases: List[AliasInfo]
    tbl_refs: Set[str]

def _eval():
    if context.segment.is_type("select_statement"):
        select_info = get_select_statement_info(context.segment, context.dialect)
        if not select_info or not select_info.table_aliases:
            return None

        crawler = SelectCrawler(context.segment, context.dialect)
        query_alias_usage: Dict[Query, AliasUsage] = dict()
        _visit_query(crawler.query_tree, query_alias_usage, context.dialect)

        for alias in query_alias_usage[crawler.query_tree].aliases:
            if alias.aliased and alias.ref_str not in query_alias_usage[crawler.query_tree].tbl_refs:
                # Unused alias. Report and fix using existing L025 code.

def _visit_query(query: Query, query_alias_usage: Dict[Query, AliasUsage], dialect: Dialect):
    # Get aliases defined in query.
    for selectable in query.selectables:
        select_info = get_select_statement_info(selectable.selectable, context.dialect)
        query_alias_usage[query].aliases += select_info.table_aliases

    # Process references.
    for r in select_info.reference_buffer:
        for tr in r.extract_possible_references(
            level=r.ObjectReferenceLevel.TABLE
        ):
            # This function walks up the query's parent stack if necessary.
            # Reuses the existing "for r in references:" loop from L025.
            resolve_and_mark_reference(query, query_alias_usage, tr.part)

    # Visit children.
    for child in query.children:
        _visit_query(child, query_alias_usage, dialect)
```
The bigquery dialect is also showing this error where the alias resolution becomes incorrect.

An aliased table in the overall selection but without a specific reference to that alias is removed, but the alias reference in the subquery still remains. This results in invalid bigquery sql.

Unfixed SQL:

```sql
SELECT col_1
, col_2
,col_3
from table_a AS a
WHERE NOT EXISTS (SELECT TRUE from table_b as b where a.col_4 = b.col_1)
```
"Fixed" SQL:

```sql
SELECT
    col_1
    , col_2
    , col_3
FROM table_a
WHERE NOT EXISTS (SELECT TRUE FROM table_b AS b WHERE a.col_4 = b.col_1)
```

Commented here as opposed to https://github.com/sqlfluff/sqlfluff/issues/2064 as it fits a little better.

Commit message: Add comment

Patch to review:
diff --git a/src/sqlfluff/core/rules/analysis/select_crawler.py b/src/sqlfluff/core/rules/analysis/select_crawler.py
index 65ed980019d..b0294c0e85d 100644
--- a/src/sqlfluff/core/rules/analysis/select_crawler.py
+++ b/src/sqlfluff/core/rules/analysis/select_crawler.py
@@ -1,7 +1,7 @@
 """Tools for more complex analysis of SELECT statements."""
 from dataclasses import dataclass, field
 from enum import Enum
-from typing import Dict, Generator, List, NamedTuple, Optional, Union
+from typing import Dict, Generator, List, NamedTuple, Optional, Type, Union
 
 from sqlfluff.core.cached_property import cached_property
 from sqlfluff.core.dialects.common import AliasInfo
@@ -85,6 +85,8 @@ class Query:
     ctes: Dict[str, "Query"] = field(default_factory=dict)
     # Parent scope. This query can "see" CTEs defined by parents.
     parent: Optional["Query"] = field(default=None)
+    # Children (could be CTE, subselect, or other).
+    children: List["Query"] = field(default_factory=list)
 
     def lookup_cte(self, name: str, pop: bool = True) -> Optional["Query"]:
         """Look up a CTE by name, in the current or any parent scope."""
@@ -146,9 +148,16 @@ class SelectCrawler:
     """Class for dependency analysis among parts of a query."""
 
     def __init__(
-        self, segment: BaseSegment, dialect: Dialect, parent: Optional[Query] = None
+        self,
+        segment: BaseSegment,
+        dialect: Dialect,
+        parent: Optional[Query] = None,
+        query_class: Type = Query,
     ):
         self.dialect: Dialect = dialect
+        # "query_class" allows users of the class to customize/extend the
+        # Query class, so they can manage additional, custom info.
+        self.query_class = query_class
         self.query_tree: Optional[Query] = None
 
         # Stack of segments currently being processed
@@ -161,6 +170,7 @@ def append_query(query):
             """Bookkeeping when a new Query is created."""
             if query_stack:
                 query.parent = query_stack[-1]
+                query.parent.children.append(query)
             query_stack.append(query)
             if len(query_stack) == 1 and self.query_tree is None:
                 self.query_tree = query_stack[0]
@@ -197,7 +207,7 @@ def finish_segment():
                             # selectables. A set_expression always has child
                             # select_statement segments, and those will be
                             # added to this Query later.
-                            query = Query(QueryType.Simple, dialect)
+                            query = self.query_class(QueryType.Simple, dialect)
                             append_query(query)
                         else:
                             # It's a select_statement.
@@ -212,14 +222,16 @@ def finish_segment():
                                 # It's a standalone select_statement, not part
                                 # of a set_expression. Create a Query containing
                                 # this select_statement.
-                                query = Query(QueryType.Simple, dialect, [selectable])
+                                query = self.query_class(
+                                    QueryType.Simple, dialect, [selectable]
+                                )
                                 append_query(query)
                     else:
                         # We're processing a "with" statement.
                         if cte_name:
                             # If we have a CTE name, this is the Query for that
                             # name.
-                            query = Query(QueryType.Simple, dialect)
+                            query = self.query_class(QueryType.Simple, dialect)
                             if path[-1].is_type("select_statement"):
                                 # Processing a select_statement. Add it to the
                                 # Query object we just created.
@@ -256,7 +268,7 @@ def finish_segment():
                                     pass
                 elif path[-1].is_type("with_compound_statement"):
                     # Beginning a "with" statement, i.e. a block of CTEs.
-                    query = Query(QueryType.WithCompound, dialect)
+                    query = self.query_class(QueryType.WithCompound, dialect)
                     if cte_name:
                         query_stack[-1].ctes[cte_name] = query
                         cte_name = None
diff --git a/src/sqlfluff/rules/L025.py b/src/sqlfluff/rules/L025.py
index acfff73dc62..b69e806582b 100644
--- a/src/sqlfluff/rules/L025.py
+++ b/src/sqlfluff/rules/L025.py
@@ -1,15 +1,36 @@
 """Implementation of Rule L025."""
 
-from sqlfluff.core.rules.base import LintFix, LintResult
+from dataclasses import dataclass, field
+from typing import cast, List, Set
+
+from sqlfluff.core.dialects.base import Dialect
+from sqlfluff.core.rules.analysis.select import get_select_statement_info
+from sqlfluff.core.rules.analysis.select_crawler import (
+    Query as SelectCrawlerQuery,
+    SelectCrawler,
+)
+from sqlfluff.core.rules.base import (
+    BaseRule,
+    LintFix,
+    LintResult,
+    RuleContext,
+    EvalResultType,
+)
 from sqlfluff.core.rules.doc_decorators import document_fix_compatible
-from sqlfluff.core.rules.functional import Segments
-import sqlfluff.core.rules.functional.segment_predicates as sp
-from sqlfluff.rules.L020 import Rule_L020
+from sqlfluff.core.rules.functional import Segments, sp
 from sqlfluff.core.dialects.common import AliasInfo
 
 
+@dataclass
+class L025Query(SelectCrawlerQuery):
+    """SelectCrawler Query with custom L025 info."""
+
+    aliases: List[AliasInfo] = field(default_factory=list)
+    tbl_refs: Set[str] = field(default_factory=set)
+
+
 @document_fix_compatible
-class Rule_L025(Rule_L020):
+class Rule_L025(BaseRule):
     """Tables should not be aliased if that alias is not used.
 
     | **Anti-pattern**
@@ -38,50 +59,78 @@ class Rule_L025(Rule_L020):
 
     """
 
-    def _lint_references_and_aliases(
-        self,
-        table_aliases,
-        standalone_aliases,
-        references,
-        col_aliases,
-        using_cols,
-        parent_select,
-    ):
-        """Check all aliased references against tables referenced in the query."""
-        # A buffer to keep any violations.
-        violation_buff = []
-        # Check all the references that we have, keep track of which aliases we refer to.
-        tbl_refs = set()
-        for r in references:
-            tbl_refs.update(
-                tr.part
-                for tr in r.extract_possible_references(
-                    level=r.ObjectReferenceLevel.TABLE
-                )
+    def _eval(self, context: RuleContext) -> EvalResultType:
+        violations: List[LintResult] = []
+        if context.segment.is_type("select_statement"):
+            # Exit early if the SELECT does not define any aliases.
+            select_info = get_select_statement_info(context.segment, context.dialect)
+            if not select_info or not select_info.table_aliases:
+                return None
+
+            # Analyze the SELECT.
+            crawler = SelectCrawler(
+                context.segment, context.dialect, query_class=L025Query
             )
+            query: L025Query = cast(L025Query, crawler.query_tree)
+            self._analyze_table_aliases(query, context.dialect)
+
+            alias: AliasInfo
+            for alias in query.aliases:
+                if alias.aliased and alias.ref_str not in query.tbl_refs:
+                    # Unused alias. Report and fix.
+                    violations.append(self._report_unused_alias(alias))
+        return violations or None
 
-        alias: AliasInfo
-        for alias in table_aliases:
-            if alias.aliased and alias.ref_str not in tbl_refs:
-                fixes = [LintFix.delete(alias.alias_expression)]
-                # Walk back to remove indents/whitespaces
-                to_delete = (
-                    Segments(*alias.from_expression_element.segments)
-                    .reversed()
-                    .select(
-                        start_seg=alias.alias_expression,
-                        # Stop once we reach an other, "regular" segment.
-                        loop_while=sp.or_(sp.is_whitespace(), sp.is_meta()),
-                    )
-                )
-                fixes += [LintFix.delete(seg) for seg in to_delete]
-                violation_buff.append(
-                    LintResult(
-                        anchor=alias.segment,
-                        description="Alias {!r} is never used in SELECT statement.".format(
-                            alias.ref_str
-                        ),
-                        fixes=fixes,
-                    )
-                )
-        return violation_buff or None
+    @classmethod
+    def _analyze_table_aliases(cls, query: L025Query, dialect: Dialect):
+        # Get table aliases defined in query.
+        for selectable in query.selectables:
+            select_info = get_select_statement_info(selectable.selectable, dialect)
+            if select_info:
+                # Record the aliases.
+                query.aliases += select_info.table_aliases
+
+                # Look at each table reference; if its an alias reference,
+                # resolve the alias: could be an alias defined in "query"
+                # itself or an "ancestor" query.
+                for r in select_info.reference_buffer:
+                    for tr in r.extract_possible_references(level=r.ObjectReferenceLevel.TABLE):  # type: ignore
+                        # This function walks up the query's parent stack if necessary.
+                        # Reuses the existing "for r in references:" loop from L025.
+                        cls._resolve_and_mark_reference(query, tr.part)
+
+        # Visit children.
+        for child in query.children:
+            cls._analyze_table_aliases(cast(L025Query, child), dialect)
+
+    @classmethod
+    def _resolve_and_mark_reference(cls, query: L025Query, ref: str):
+        # Does this query define the referenced alias?
+        if any(ref == a.ref_str for a in query.aliases):
+            # Yes. Record the reference.
+            query.tbl_refs.add(ref)
+        elif query.parent:
+            # No. Recursively check the query's parent hierarchy.
+            cls._resolve_and_mark_reference(cast(L025Query, query.parent), ref)
+
+    @classmethod
+    def _report_unused_alias(cls, alias: AliasInfo) -> LintResult:
+        fixes = [LintFix.delete(alias.alias_expression)]  # type: ignore
+        # Walk back to remove indents/whitespaces
+        to_delete = (
+            Segments(*alias.from_expression_element.segments)
+            .reversed()
+            .select(
+                start_seg=alias.alias_expression,
+                # Stop once we reach an other, "regular" segment.
+                loop_while=sp.or_(sp.is_whitespace(), sp.is_meta()),
+            )
+        )
+        fixes += [LintFix.delete(seg) for seg in to_delete]
+        return LintResult(
+            anchor=alias.segment,
+            description="Alias {!r} is never used in SELECT statement.".format(
+                alias.ref_str
+            ),
+            fixes=fixes,
+        )
diff --git a/src/sqlfluff/rules/L026.py b/src/sqlfluff/rules/L026.py
index b096e447357..1cd2c347614 100644
--- a/src/sqlfluff/rules/L026.py
+++ b/src/sqlfluff/rules/L026.py
@@ -3,7 +3,7 @@
 from sqlfluff.core.rules.analysis.select import get_aliases_from_select
 from sqlfluff.core.rules.base import EvalResultType, LintResult, RuleContext
 from sqlfluff.core.rules.doc_decorators import document_configuration
-from sqlfluff.rules.L025 import Rule_L020
+from sqlfluff.rules.L020 import Rule_L020
 
 
 @document_configuration
diff --git a/src/sqlfluff/rules/L028.py b/src/sqlfluff/rules/L028.py
index c82d326da79..8d0b7f54bb1 100644
--- a/src/sqlfluff/rules/L028.py
+++ b/src/sqlfluff/rules/L028.py
@@ -2,11 +2,11 @@
 
 from sqlfluff.core.rules.base import LintResult, EvalResultType, RuleContext
 from sqlfluff.core.rules.doc_decorators import document_configuration
-from sqlfluff.rules.L025 import Rule_L025
+from sqlfluff.rules.L020 import Rule_L020
 
 
 @document_configuration
-class Rule_L028(Rule_L025):
+class Rule_L028(Rule_L020):
     """References should be consistent in statements with a single table.
 
     NB: This rule is disabled by default for BigQuery due to its use of
@@ -103,7 +103,7 @@ def _lint_references_and_aliases(
         return violation_buff or None
 
     def _eval(self, context: RuleContext) -> EvalResultType:
-        """Override Rule L025 for dialects that use structs, or SELECT aliases."""
+        """Override base class for dialects that use structs, or SELECT aliases."""
         # Config type hints
         self.force_enable: bool
 
diff --git a/test/fixtures/rules/std_rule_cases/L025.yml b/test/fixtures/rules/std_rule_cases/L025.yml
index 4284936ab9b..e10f89bab75 100644
--- a/test/fixtures/rules/std_rule_cases/L025.yml
+++ b/test/fixtures/rules/std_rule_cases/L025.yml
@@ -76,3 +76,29 @@ test_pass_tsql_object_reference_override:
   configs:
     core:
       dialect: tsql
+
+test_pass_subselect_uses_alias_1:
+  pass_str: |
+    SELECT
+        col1,
+        (
+            SELECT count(*)
+            FROM base
+            WHERE a.col2 = base.col2
+        )
+    FROM
+        without_dup AS a
+
+test_pass_subselect_uses_alias_2:
+  pass_str: |
+    select
+      COL_A
+      , COL_B
+    from INSERTS INS
+    where COL_B != (select max(COL_B) from INSERTS X where INS.COL_A = X.COL_A)
+
+test_pass_subselect_uses_alias_3:
+  pass_str: |
+    SELECT col_1
+    FROM table_a AS a
+    WHERE NOT EXISTS (SELECT TRUE FROM table_b AS b WHERE a.col_4 = b.col_1)


Code review comments:
diff_hunk: @@ -38,50 +59,78 @@ class Rule_L025(Rule_L020):
 
     """
 
-    def _lint_references_and_aliases(
-        self,
-        table_aliases,
-        standalone_aliases,
-        references,
-        col_aliases,
-        using_cols,
-        parent_select,
-    ):
-        """Check all aliased references against tables referenced in the query."""
-        # A buffer to keep any violations.
-        violation_buff = []
-        # Check all the references that we have, keep track of which aliases we refer to.
-        tbl_refs = set()
-        for r in references:
-            tbl_refs.update(
-                tr.part
-                for tr in r.extract_possible_references(
-                    level=r.ObjectReferenceLevel.TABLE
-                )
+    def _eval(self, context: RuleContext) -> EvalResultType:
+        violations: List[LintResult] = []
+        if context.segment.is_type("select_statement"):
+            # Exit early if the SELECT does not define any aliases.
+            select_info = get_select_statement_info(context.segment, context.dialect)
+            if not select_info or not select_info.table_aliases:
+                return None
+
+            # Analyze the SELECT.
+            crawler = SelectCrawler(
+                context.segment, context.dialect, query_class=L025Query
             )
+            query: L025Query = cast(L025Query, crawler.query_tree)
+            self._analyze_table_aliases(query, context.dialect)
+
+            alias: AliasInfo
+            for alias in query.aliases:
+                if alias.aliased and alias.ref_str not in query.tbl_refs:
+                    # Unused alias. Report and fix.
+                    violations.append(self._report_unused_alias(alias))
+        return violations or None
 
-        alias: AliasInfo
-        for alias in table_aliases:
-            if alias.aliased and alias.ref_str not in tbl_refs:
-                fixes = [LintFix.delete(alias.alias_expression)]
-                # Walk back to remove indents/whitespaces
-                to_delete = (
-                    Segments(*alias.from_expression_element.segments)
-                    .reversed()
-                    .select(
-                        start_seg=alias.alias_expression,
-                        # Stop once we reach an other, "regular" segment.
-                        loop_while=sp.or_(sp.is_whitespace(), sp.is_meta()),
-                    )
-                )
-                fixes += [LintFix.delete(seg) for seg in to_delete]
-                violation_buff.append(
-                    LintResult(
-                        anchor=alias.segment,
-                        description="Alias {!r} is never used in SELECT statement.".format(
-                            alias.ref_str
-                        ),
-                        fixes=fixes,
-                    )
-                )
-        return violation_buff or None
+    @classmethod
+    def _analyze_table_aliases(cls, query: L025Query, dialect: Dialect):
+        # Get table aliases defined in query.
+        for selectable in query.selectables:
+            select_info = get_select_statement_info(selectable.selectable, dialect)
+            if select_info:
+                # Record the aliases.
+                query.aliases += select_info.table_aliases
+
+                # Look at each table reference; if its an alias reference,
+                # resolve the alias: could be an alias defined in "query"
+                # itself or an "ancestor" query.
+                for r in select_info.reference_buffer:
+                    for tr in r.extract_possible_references(level=r.ObjectReferenceLevel.TABLE):  # type: ignore
+                        # This function walks up the query's parent stack if necessary.
+                        # Reuses the existing "for r in references:" loop from L025.
path: src/sqlfluff/rules/L025.py
text: @user1:
Should we remove this line?

```suggestion
```

@author:
Oh yes -- that's left over from my pseudocode.