Repository: sqlfluff/sqlfluff
Pull request: Parse a and not b expression
Resolves #827 and #874

This logic change is causing a maximum recursion depth exceeded error in test cases `expression_recursion.sql` and `expression_recursion_2.sql`. I have increased the max depth to accommodate the increase.

Curious for your thoughts @barrywhart @dmateusp @alanmcruickshank 

Problem statement:
ANSI dialect can't parse expression with "AND NOT", e.g. "SELECT  a AND NOT i.b FROM i"
-- 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. Finally, please add any labels that are related to the issue before submitting so that it can be addressed easily! --

## Expected Behaviour
this is the part of the query it's saying is missing an AS alias
```
  i.item_upc IS NOT NULL
  AND i.item_upc NOT IN ('000000000000', '1', '')
  AND NOT i.is_excluded_upc
  AND COALESCE(i.linked_error NOT ILIKE '%there is already an item from%', TRUE) AS has_linkable_upc,
```
## Observed Behaviour
and its inserting the AS after the `AND NOT` which is not correct.
```
  i.item_upc IS NOT NULL
  AND i.item_upc NOT IN ('000000000000', '1', '')
  AND NOT AS i.is_excluded_upc
  AND COALESCE(i.linked_error NOT ILIKE '%there is already an item from%', TRUE) AS has_linkable_upc,
```
## Steps to Reproduce
sqlfluff lint and sqlfluff fix

## Version
Include the output of `sqlfluff --version` along with your Python version
sqlfluff, version 0.4.1
Python 2.7.16

## Configuration
```
[sqlfluff]
verbose = 0
nocolor = False
dialect = snowflake
templater = jinja
rules = L010,L012,L023,L030
exclude_rules = None
recurse = 0
output_line_length = 80
ignore = parsing,templating

[sqlfluff:indentation]
indented_joins = False

[sqlfluff:templater:jinja]
apply_dbt_builtins = True
load_macros_from_path=dbt/macros/parsing

[sqlfluff:templater:jinja:macros]
# Macros provided as builtins for dbt projects
dbt_ref = {% macro ref(model_ref) %}{{model_ref}}{% endmacro %}
dbt_source = {% macro source(source_name, table) %}{{source_name}}_{{table}}{% endmacro %}
dbt_config = {% macro config() %}{% for k in kwargs %}{% endfor %}{% endmacro %}
dbt_var = {% macro var(variable) %}item{% endmacro %}

# Some rules can be configured directly from the config common to other rules.
[sqlfluff:rules]
tab_space_size = 2
max_line_length = 80
indent_unit = space
comma_style = trailing
allow_scalar = True
single_table_references = consistent
only_aliases = True

# Some rules have their own specific config

#inconsistent capitalization of keywords
[sqlfluff:rules:L010]
capitalisation_policy = upper

#unquoted identifiers
[sqlfluff:rules:L014]
capitalisation_policy = consistent

#uppercase functions
[sqlfluff:rules:L030]
capitalisation_policy = upper

```

Hints from issue discussion:
Can you provide an entire query which demonstrates the problem? It can be a "toy" query, but having a complete query makes it much easier for us to reproduce and fix problems. Thanks!
> Can you provide an entire query which demonstrates the problem? It can be a "toy" query, but having a complete query makes it much easier for us to reproduce and fix problems. Thanks!

sure, here the whole query. the snippit i added in the description shows where the problem is occurring in the query. 

```
SELECT
  i.snapshot_date,
  i.store_id,
  i.quantity_left > 0 AS in_stock,
  i.show_in_catalog AS is_shown_in_catalog,
  i.master_item_id IS NOT NULL AS is_linked,
  COALESCE(DATEDIFF('DAYS', i.last_moved_at, i.snapshot_date) <= 60, FALSE) AS is_moving_60,

  i.item_upc IS NOT NULL
  AND i.item_upc NOT IN ('000000000000', '1', '')
  AND NOT i.is_excluded_upc
  AND COALESCE(i.linked_error NOT ILIKE '%there is already an item from%', TRUE) AS has_linkable_upc,

  i.is_available,
  COUNT(i.item_id) AS item_count

FROM {{ ref('items_snapshot_all') }} i

WHERE i.has_active_inventory_set
  AND i.snapshot_date > '2020-07-07'::DATE

  {% if is_incremental() %}

    AND i.snapshot_date > (SELECT MAX(snapshot_date)::DATE FROM {{ this }})

  {% endif %}

GROUP BY 1,2,3,4,5,6,7,8
```
Thanks @emily-hawkins! I took your test query and was able to reproduce the problem.

I gradually removed parts of the query to find a minimal example. Here's what I learned:
* This is a an issue in SQLFluff's parsing. SQLFluff is not understanding the `something AND NOT something_else` syntax.
* The same issue occurs in the base ANSI dialect, so the issue is not specific to Snowflake.
* You're seeing L012 make an invalid change to the query because in general, SQLFluff still runs the linter rules even if parsing fails. So it's misinterpreting the word `NOT` as a column name and `i.is_excluded_upc` as an alias.

Here's the minimal query I created. Running `sqlfluff parse` on this file without a `.sqlfluff` file present has the same parse issue as your query.

```
SELECT
  a AND NOT i.b
FROM i
```
@emily-hawkins: As a workaround, if you add parentheses, it will parse correctly, i.e. replace this:
`NOT i.is_excluded_upc`

with this:
`(NOT i.is_excluded_upc)`
> @emily-hawkins: As a workaround, if you add parentheses, it will parse correctly, i.e. replace this:
> `NOT i.is_excluded_upc`
> 
> with this:
> `(NOT i.is_excluded_upc)`

thanks for the tip!
I've reviewed the ANSI grammar and identified an areas of potential focus for fixing the bug.

Around line 1241:
```
                Sequence(
                    # e.g. NOT EXISTS, but other expressions could be met as
                    # well by inverting the condition with the NOT operator
                    Ref.keyword("NOT", optional=True),
                    #"NOT",
                    Ref("Expression_C_Grammar"),
                ),
```

Here, I've changed `"NOT"` to `Ref.keyword("NOT", optional=True)`. With this change, the query parses, but the parse looks incorrect. Notice that `NOT` is parsed as a `column_reference`. When it is parsed correctly (e.g. before an `AND`, it parses as a `keyword`.

```
[9](1, 2, 3)        |                    expression:
[9](1, 2, 3)        |                        column_reference:
[9](1, 2, 3)        |                            identifier:                       'a'
[10](1, 2, 4)       |                        whitespace:                           ' '
[11](1, 2, 5)       |                        binary_operator:                      'AND'
[14](1, 2, 8)       |                        newline:                              '\n'
[15](1, 3, 1)       |                        whitespace:                           '  '
[17](1, 3, 3)       |                        column_reference:
[17](1, 3, 3)       |                            identifier:                       'NOT'
[20](1, 3, 6)       |                        whitespace:                           ' '
[21](1, 3, 7)       |                        column_reference:
[21](1, 3, 7)       |                            identifier:                       'i'
[22](1, 3, 8)       |                            dot:                              '.'
[23](1, 3, 9)       |                            identifier:                       'b'
```

Commit message: Lint

Patch to review:
diff --git a/src/sqlfluff/__init__.py b/src/sqlfluff/__init__.py
index 876ff74c001..32076acb782 100644
--- a/src/sqlfluff/__init__.py
+++ b/src/sqlfluff/__init__.py
@@ -20,6 +20,9 @@
 import pkg_resources
 import configparser
 
+# Increase the maximum recursion depth from default of 10^4 to 10^5, see https://github.com/sqlfluff/sqlfluff/pull/870
+sys.setrecursionlimit(10 ** 5)
+
 # Get the current version
 config = configparser.ConfigParser()
 config.read([pkg_resources.resource_filename("sqlfluff", "config.ini")])
diff --git a/src/sqlfluff/core/dialects/dialect_ansi.py b/src/sqlfluff/core/dialects/dialect_ansi.py
index 2c1f7a62657..88a9f04a767 100644
--- a/src/sqlfluff/core/dialects/dialect_ansi.py
+++ b/src/sqlfluff/core/dialects/dialect_ansi.py
@@ -1204,7 +1204,7 @@ class CaseExpressionSegment(BaseSegment):
                         )
                         # We need to add a lot more here...
                     ),
-                    Ref("Expression_C_Grammar"),
+                    Ref("Expression_A_Grammar"),
                     Sequence(
                         Ref.keyword("ESCAPE"),
                         Ref("Expression_C_Grammar"),
diff --git a/test/fixtures/parser/ansi/select_a_and_not_b.sql b/test/fixtures/parser/ansi/select_a_and_not_b.sql
new file mode 100644
index 00000000000..65e5b46a415
--- /dev/null
+++ b/test/fixtures/parser/ansi/select_a_and_not_b.sql
@@ -0,0 +1,5 @@
+-- https://github.com/sqlfluff/sqlfluff/issues/827
+
+SELECT
+  a AND NOT i.b
+FROM i
\ No newline at end of file
diff --git a/test/fixtures/parser/ansi/select_a_and_not_b.yml b/test/fixtures/parser/ansi/select_a_and_not_b.yml
new file mode 100644
index 00000000000..c1453f1193e
--- /dev/null
+++ b/test/fixtures/parser/ansi/select_a_and_not_b.yml
@@ -0,0 +1,21 @@
+file:
+  statement:
+    select_statement:
+      select_clause:
+        keyword: SELECT
+        select_target_element:
+          expression:
+          - column_reference:
+              identifier: a
+          - binary_operator: AND
+          - keyword: NOT
+          - column_reference:
+            - identifier: i
+            - dot: .
+            - identifier: b
+      from_clause:
+        keyword: FROM
+        table_expression:
+          main_table_expression:
+            table_reference:
+              identifier: i
diff --git a/test/fixtures/parser/ansi/select_true_and_not_false.sql b/test/fixtures/parser/ansi/select_true_and_not_false.sql
new file mode 100644
index 00000000000..657f0ea9c73
--- /dev/null
+++ b/test/fixtures/parser/ansi/select_true_and_not_false.sql
@@ -0,0 +1,2 @@
+-- https://github.com/sqlfluff/sqlfluff/issues/874
+SELECT TRUE AND NOT FALSE
\ No newline at end of file
diff --git a/test/fixtures/parser/ansi/select_true_and_not_false.yml b/test/fixtures/parser/ansi/select_true_and_not_false.yml
new file mode 100644
index 00000000000..b4bdd6ddf49
--- /dev/null
+++ b/test/fixtures/parser/ansi/select_true_and_not_false.yml
@@ -0,0 +1,11 @@
+file:
+  statement:
+    select_statement:
+      select_clause:
+        keyword: SELECT
+        select_target_element:
+          expression:
+          - literal: 'TRUE'
+          - binary_operator: AND
+          - keyword: NOT
+          - literal: 'FALSE'


Code review comments:
diff_hunk: @@ -20,6 +20,9 @@
 import pkg_resources
 import configparser
 
+# Increase the maximum recursion depth from default of 10^4 to 10^5, see https://github.com/sqlfluff/sqlfluff/pull/870
+sys.setrecursionlimit(10 ** 5)
path: src/sqlfluff/__init__.py
text: @user1:
TBH, I'm surprised that increasing it to such a high number:
* Is necessary
* Works

Usually, if I write code that recurses this deeply, it's because of accidental _infinite_ recursion. Do we have a sense for why the parser recurses so deeply but eventually does the right thing and stops?

@user1:
TBH, I don't know what units this number is in. I had naively assumed it is the number of function calls. Is it possible it's something else, such as bytes, e.g. the amount of storage taken up the stack, local variables, ??