Question: Is it possible to match a subsequence multiple times?

[barrywhart]

Hi! I'm evaluating awesome-pattern-matching for use in the SQLFluff SQL linter package. When we write rules to lint SQL code, we often need to search the parse tree for patterns, and your package seems like a potentially great fit.

I've gotten some basic patterns working, but I'm struggling with this one, and I wonder if it's supported.

A SQL CASE statement can have multiple WHEN clauses, e.g.:

            CASE
                WHEN species = 'Dog' THEN 'Woof'
                WHEN species = 'Mouse' THEN 'Squeak'
            END

I'd like a pattern that matches any number of WHEN segments in a sequence of parse nodes. The WHEN segments are mingled with other segments.

This works:

                    match = match(
                        matched["nested_case_expression"].segments,
                        [
                            Some(...),
                            "when1" @ Check(sp.is_keyword(("when"))),
                            Some(...),
                        ]
                    )

And this works:

                    match = match(
                        matched["nested_case_expression"].segments,
                        [
                            Some(...),
                            "when1" @ Check(sp.is_keyword(("when"))),
                            Some(...),
                            "when2" @ Check(sp.is_keyword(("when"))),
                            Some(...),
                        ]
                    )

But I don't know how to create a pattern for the general case. For example, this attempt does not work:

                    match = match(
                        matched["nested_case_expression"].segments,
                        [
                            Some(
                                [
                                    Some(...),
                                    "when1" @ Check(sp.is_keyword(("when"))),
                                ]
                            ),
                            Some(...),
                        ]
                    )

Do you know of a way to do this?

[scravy]

Hi @barrywhart

This is currently not possible. Some(...) is matching items, so the last example is matching sublists, not subsequences as you intend to.

This is a great feature though, I have started working on it in #9

[barrywhart]

That's great news, thanks!!

[scravy]

This is now possible.

I have added a test case for your specific example: https://github.com/scravy/awesome-pattern-matching/blob/main/tests/test_issues.py#L104

Here's the description of the new feature:

This allows Some(*) to match subsequences.

Previously Some(...) would only match individiual items, i.e. the pattern [0, Some(1), 2] would match the value [0, 1, 1, 1, 2]. Compared with a regex on strings this would be like 01*2 but the repetition here could not be applied to subsequences 0(12)*3. This pull request introduces the ability for Some(*) to take multiple patterns which it then tries to match as a sequence within: [0, Some(1, 2), 3] would now match the value [0, 1, 2, 1, 2, 3]. This could not be expressed before.

Note that the new syntax is different from Some([1, 2]) as this would match items which are themselves lists, i.e. [0, [1, 2], [1, 2], 3].

[scravy]

@barrywhart If you like you can check out the repository and check it with a local build. I do let this sink in a bit as I did quite a bit of refactoring to accommodate this use case – I'll release 0.23.0 eventually

Maybe you can help me understand something: I am interested in how you plan on extracting things once you matched them? For me apm was always a great tool to not just match but also extract data. The test case added has a simple extraction and I don't know the structure of your AST, so I just used strings and a simple predicate on them.

Note that if you plan on using this library it might make sense to extract some common patterns as described in the short paragraph about extensibility in the README: https://github.com/scravy/awesome-pattern-matching#extensible – basically a Check(sp.is_keyword(...)) could be Keyword("when")

[barrywhart]

Thanks, @scravy! I hope to try it this week.

Yes, we will make extensive use of the @ operator to extract parts of the matches. The project we'd be using it on is a SQL linter/fixer. The project already has 50+ rules. We're looking for ways to make it easier and faster to create rules, and we think awesome-pattern-matching could be very helpful.

Lint rules detect issues in SQL code and optionally fix them. So the typical usage of awesome-pattern-matching would be:

• Use match() to search for pattern(s). The pattern alone may be enough to detect issues, or there may be additional code to confirm an issue.
• Extract the matched elements to help build proposed fixes for the issue.

Here are a few examples of rules that I rewrote using awesome-pattern-matching. These examples don't rely on the fix in this issue, but should give you an idea how we'll use it.

"""Implementation of Rule L017."""

from apm import match, Check, Some

from sqlfluff.core.rules.base import BaseRule, LintFix, LintResult, RuleContext
from sqlfluff.core.rules.doc_decorators import document_fix_compatible
from sqlfluff.core.rules.functional import sp


@document_fix_compatible
class Rule_L017(BaseRule):
    """Function name not immediately followed by bracket.

    | **Anti-pattern**
    | In this example, there is a space between the function and the parenthesis.

    .. code-block:: sql

        SELECT
            sum (a)
        FROM foo

    | **Best practice**
    | Remove the space between the function and the parenthesis.

    .. code-block:: sql

        SELECT
            sum(a)
        FROM foo

    """

    def _eval(self, context: RuleContext) -> LintResult:
        """Function name not immediately followed by bracket.

        Look for Function Segment with anything other than the
        function name before brackets
        """
        segment = context.functional.segment
        # We only trigger on start_bracket (open parenthesis)
        if segment.all(sp.is_type("function")):
            matched = match(
                segment.children(),
                [
                    "fn_name" @ Check(sp.is_type("function_name")),
                    "between"
                    @ Some(Check(sp.not_(sp.is_type("bracketed"))), at_least=1),
                    "bracket" @ Check(sp.is_type("bracketed")),
                ],
            )
            if matched:
                fixes = None
                if all(
                    seg.is_type("whitespace", "newline") for seg in matched["between"]
                ):
                    # Fix if there is only whitespace or newlines between.
                    fixes = [LintFix.delete(seg) for seg in matched["between"]]

                return LintResult(
                    anchor=matched["between"][0],
                    fixes=fixes,
                )
        return LintResult()

"""Implementation of Rule L041."""
from typing import Optional

from apm import match, Check, Some

from sqlfluff.core.parser import NewlineSegment, WhitespaceSegment
from sqlfluff.core.rules.base import BaseRule, LintFix, LintResult, RuleContext
from sqlfluff.core.rules.doc_decorators import document_fix_compatible
import sqlfluff.core.rules.functional.segment_predicates as sp


@document_fix_compatible
class Rule_L041(BaseRule):
    """SELECT clause modifiers such as DISTINCT must be on the same line as SELECT.

    | **Anti-pattern**

    .. code-block:: sql

        select
            distinct a,
            b
        from x


    | **Best practice**

    .. code-block:: sql

        select distinct
            a,
            b
        from x

    """

    def _eval(self, context: RuleContext) -> Optional[LintResult]:
        """Select clause modifiers must appear on same line as SELECT."""
        if context.segment.is_type("select_clause"):
            # Use "awesome-pattern-matching" package to scan child segments for
            # violations, i.e. occurrences of this pattern (other segments may
            # appears between each of these):
            # 1. SELECT keyword
            # 2. Newline
            # 3. Select modifier, e.g. "DISTINCT"
            matched = match(
                context.segment.segments,
                [
                    # 1. SELECT keyword
                    Check(
                        sp.and_(
                            sp.is_type("keyword"),
                            lambda seg: seg.raw.lower() == "select",
                        )
                    ),
                    Some(Check(sp.not_(sp.is_type("newline"))), at_least=0),
                    # 2. Newline
                    "newline" @ Check(sp.is_type("newline")),
                    Some(
                        Check(sp.not_(sp.is_type("select_clause_modifier"))), at_least=0
                    ),
                    # 3. Select modifier, e.g. "DISTINCT"
                    "modifier" @ Check(sp.is_type("select_clause_modifier")),
                    Some(...),
                ],
            )
            if not matched:
                return None

            # We found a pattern match, thus there's an issue.
            newline_between = matched["newline"]
            newline_idx = context.segment.segments.index(newline_between)
            select_modifier = matched["modifier"]

            # E.g.: " DISTINCT\n"
            replace_newline_with = [
                WhitespaceSegment(),
                select_modifier,
                NewlineSegment(),
            ]
            fixes = [
                # E.g. "\n" -> " DISTINCT\n.
                LintFix.delete(newline_between),
                LintFix.create_before(
                    context.segment.segments[newline_idx + 1],
                    replace_newline_with,
                ),
                # E.g. "DISTINCT" -> X
                LintFix.delete(select_modifier),
            ]

            # E.g. " " after "DISTINCT"
            ws_to_delete = context.segment.select_children(
                start_seg=select_modifier,
                select_if=lambda s: s.is_type("whitespace"),
                loop_while=lambda s: s.is_type("whitespace") or s.is_meta,
            )

            # E.g. " " -> X
            fixes += [LintFix.delete(ws) for ws in ws_to_delete]
            return LintResult(
                anchor=context.segment,
                fixes=fixes,
            )

        return None

"""Implementation of Rule L049."""
from typing import Tuple

from apm import match, Check, Some

from sqlfluff.core.parser import KeywordSegment, RawSegment, WhitespaceSegment
from sqlfluff.core.rules.base import LintResult, LintFix, RuleContext
from sqlfluff.core.rules.doc_decorators import document_fix_compatible
import sqlfluff.core.rules.functional.segment_predicates as sp
from sqlfluff.rules.L006 import Rule_L006


@document_fix_compatible
class Rule_L049(Rule_L006):
    """Comparisons with NULL should use "IS" or "IS NOT".

    | **Anti-pattern**
    | In this example, the "=" operator is used to check for NULL values'.

    .. code-block:: sql

        SELECT
            a
        FROM foo
        WHERE a = NULL


    | **Best practice**
    | Use "IS" or "IS NOT" to check for NULL values.

    .. code-block:: sql

        SELECT
            a
        FROM foo
        WHERE a IS NULL
    """

    def _eval(self, context: RuleContext) -> LintResult:
        """Relational operators should not be used to check for NULL values."""
        # Context/motivation for this rule:
        # https://news.ycombinator.com/item?id=28772289
        # https://stackoverflow.com/questions/9581745/sql-is-null-and-null
        if len(context.segment.segments) <= 2:
            return LintResult()

        # Allow assignments in SET clauses
        if context.parent_stack and context.parent_stack[-1].is_type("set_clause_list"):
            return LintResult()

        children = context.functional.segment.children()
        matched = match(
            children,
            [
                Some(Check(sp.not_(sp.is_name("equals", "not_equal_to"))), at_least=0),
                # "=" or "<>"
                "operator" @ Check(sp.is_name("equals", "not_equal_to")),
                Some(Check(sp.not_(sp.is_name("null_literal"))), at_least=0),
                # "NULL" literal
                "null" @ Check(sp.is_name("null_literal")),
                Some(...),
            ],
        )
        if not matched:
            return LintResult()

        if matched["null"].raw[0] == "N":
            is_seg = KeywordSegment("IS")
            not_seg = KeywordSegment("NOT")
        else:
            is_seg = KeywordSegment("is")
            not_seg = KeywordSegment("not")

        edit: Tuple[RawSegment, ...] = (
            (is_seg,)
            if matched["operator"].name == "equals"
            else (
                is_seg,
                WhitespaceSegment(),
                not_seg,
            )
        )
        idx_operator = children.index(matched["operator"])
        prev_seg = self._find_segment(
            idx_operator, context.segment.segments, before=True
        )
        if self._missing_whitespace(prev_seg, before=True):
            edit = (WhitespaceSegment(),) + edit
        next_seg = self._find_segment(
            idx_operator, context.segment.segments, before=False
        )
        if self._missing_whitespace(next_seg, before=False):
            edit = edit + (WhitespaceSegment(),)
        return LintResult(
            anchor=matched["operator"],
            fixes=[
                LintFix.replace(
                    matched["operator"],
                    edit,
                )
            ],
        )

"""Implementation of Rule L052."""
from typing import Optional, Tuple

from apm import match, Check, Some

from sqlfluff.core.parser import SymbolSegment
from sqlfluff.core.parser.segments.base import BaseSegment
from sqlfluff.core.parser.segments.raw import NewlineSegment

from sqlfluff.core.rules.base import BaseRule, LintResult, LintFix, RuleContext
from sqlfluff.core.rules.doc_decorators import (
    document_configuration,
    document_fix_compatible,
)
import sqlfluff.core.rules.functional.segment_predicates as sp


@document_configuration
@document_fix_compatible
class Rule_L052(BaseRule):
    """Statements must end with a semi-colon.

    | **Anti-pattern**
    | A statement is not immediately terminated with a semi-colon, the • represents space.

    .. code-block:: sql
       :force:

        SELECT
            a
        FROM foo

        ;

        SELECT
            b
        FROM bar••;

    | **Best practice**
    | Immediately terminate the statement with a semi-colon.

    .. code-block:: sql
       :force:

        SELECT
            a
        FROM foo;
    """

    config_keywords = ["multiline_newline", "require_final_semicolon"]

    @staticmethod
    def _handle_preceding_inline_comments(pre_semicolon_segments, anchor_segment):
        """Adjust pre_semicolon_segments and anchor_segment to not move preceding inline comments.

        We don't want to move inline comments that are on the same line
        as the preceding code segment as they could contain noqa instructions.
        """
        # See if we have a preceding inline comment on the same line as the preceding segment.
        same_line_comment = next(
            (
                s
                for s in pre_semicolon_segments
                if s.is_comment
                and s.name != "block_comment"
                and s.pos_marker.working_line_no
                == anchor_segment.pos_marker.working_line_no
            ),
            None,
        )
        # If so then make that our new anchor segment and adjust
        # pre_semicolon_segments accordingly.
        if same_line_comment:
            anchor_segment = same_line_comment
            pre_semicolon_segments = pre_semicolon_segments[
                : pre_semicolon_segments.index(same_line_comment)
            ]

        return pre_semicolon_segments, anchor_segment

    @staticmethod
    def _handle_trailing_inline_comments(context, anchor_segment):
        """Adjust anchor_segment to not move trailing inline comment.

        We don't want to move inline comments that are on the same line
        as the preceding code segment as they could contain noqa instructions.
        """
        # See if we have a trailing inline comment on the same line as the preceding segment.
        for parent_segment in context.parent_stack[::-1]:
            for comment_segment in parent_segment.recursive_crawl("comment"):
                if (
                    comment_segment.pos_marker.working_line_no
                    == anchor_segment.pos_marker.working_line_no
                ) and (comment_segment.name != "block_comment"):
                    anchor_segment = comment_segment

        return anchor_segment

    @staticmethod
    def _is_one_line_statement(context, segment):
        """Check if the statement containing the provided segment is one line."""
        # Find statement segment containing the current segment.
        statement_segment = next(
            (
                s
                for s in context.parent_stack[0].path_to(segment)
                if s.is_type("statement")
            ),
            None,
        )
        if statement_segment is None:  # pragma: no cover
            # If we can't find a parent statement segment then don't try anything special.
            return False

        if not any(statement_segment.recursive_crawl("newline")):
            # Statement segment has no newlines therefore starts and ends on the same line.
            return True

        return False

    def _eval(self, context: RuleContext) -> Optional[LintResult]:
        """Statements must end with a semi-colon."""
        # Config type hints
        self.multiline_newline: bool
        self.require_final_semicolon: bool

        # First we can simply handle the case of existing semi-colon alignment.
        if context.segment.name == "semicolon":

            # Locate semicolon and search back over the raw stack
            # to find the end of the preceding statement.
            reversed_raw_stack = context.functional.raw_stack.reversed()
            before_code = reversed_raw_stack.select(loop_while=sp.not_(sp.is_code()))
            anchor_segment = before_code[-1] if before_code else context.segment

            # We can tidy up any whitespace between the semi-colon
            # and the preceding code/comment segment.
            # Don't mess with comment spacing/placement.
            pre_semicolon_segments = before_code.select(sp.not_(sp.is_meta()))
            whitespace_deletions = pre_semicolon_segments.select(
                loop_while=sp.is_whitespace()
            )

            # Semi-colon on same line.
            first_code = reversed_raw_stack.select(sp.is_code()).first()
            is_one_line = self._is_one_line_statement(context, first_code[0])
            semicolon_newline = self.multiline_newline if not is_one_line else False
            if not semicolon_newline:
                if len(pre_semicolon_segments) >= 1:
                    # If preceding segments are found then delete the old
                    # semi-colon and its preceding whitespace and then insert
                    # the semi-colon in the correct location.
                    fixes = [
                        LintFix.replace(
                            anchor_segment,
                            [
                                anchor_segment,
                                SymbolSegment(raw=";", type="symbol", name="semicolon"),
                            ],
                        ),
                        LintFix.delete(
                            context.segment,
                        ),
                    ]
                    fixes.extend(LintFix.delete(d) for d in whitespace_deletions)
                    return LintResult(
                        anchor=anchor_segment,
                        fixes=fixes,
                    )
            # Semi-colon on new line.
            else:
                # Adjust pre_semicolon_segments and anchor_segment for preceding inline comments.
                # Inline comments can contain noqa logic so we need to add the newline after the inline comment.
                (
                    pre_semicolon_segments,
                    anchor_segment,
                ) = self._handle_preceding_inline_comments(
                    pre_semicolon_segments, anchor_segment
                )

                if not (
                    (len(pre_semicolon_segments) == 1)
                    and all(s.is_type("newline") for s in pre_semicolon_segments)
                ):
                    # If preceding segment is not a single newline then delete the old
                    # semi-colon/preceding whitespace and then insert the
                    # semi-colon in the correct location.

                    # This handles an edge case in which an inline comment comes after the semi-colon.
                    anchor_segment = self._handle_trailing_inline_comments(
                        context, anchor_segment
                    )

                    fixes = [
                        LintFix.replace(
                            anchor_segment,
                            [
                                anchor_segment,
                                NewlineSegment(),
                                SymbolSegment(raw=";", type="symbol", name="semicolon"),
                            ],
                        ),
                        LintFix.delete(
                            context.segment,
                        ),
                    ]
                    fixes.extend(LintFix.delete(d) for d in whitespace_deletions)
                    return LintResult(
                        anchor=anchor_segment,
                        fixes=fixes,
                    )

        # SQL does not require a final trailing semi-colon, however
        # this rule looks to enforce that it is there.
        if self.require_final_semicolon:
            # Locate the end of the file.
            if not self.is_final_segment(context):
                return None

            # Include current segment for complete stack.
            complete_stack: Tuple[BaseSegment, ...] = tuple(context.raw_stack) + (
                context.segment,
            )

            # Iterate backwards over complete stack to find
            # if the final semi-colon is already present.
            matched = match(
                reversed(complete_stack),
                [
                    "before"
                    @ Some(
                        Check(sp.or_(sp.not_(sp.is_code()), sp.is_name("semicolon")))
                    ),
                    "code"
                    @ Check(sp.and_(sp.is_code(), sp.not_(sp.is_name("semicolon")))),
                    Some(...),
                ],
            )
            if not matched:
                return None  # pragma: no cover

            anchor_segment = (
                matched["before"][-1] if matched["before"] else context.segment
            )
            semicolon_newline = (
                self.multiline_newline
                if not self._is_one_line_statement(context, matched["code"])
                else False
            )

            if not any(seg.is_name("semicolon") for seg in matched["before"]):
                # Create the final semi-colon if it does not yet exist.

                # Semi-colon on same line.
                if not semicolon_newline:
                    fixes = [
                        LintFix.replace(
                            anchor_segment,
                            [
                                anchor_segment,
                                SymbolSegment(raw=";", type="symbol", name="semicolon"),
                            ],
                        )
                    ]
                # Semi-colon on new line.
                else:
                    # Adjust anchor_segment for inline comments.
                    anchor_segment = self._handle_preceding_inline_comments(
                        [seg for seg in matched["before"] if not seg.is_meta],
                        anchor_segment,
                    )[1]
                    fixes = [
                        LintFix.replace(
                            anchor_segment,
                            [
                                anchor_segment,
                                NewlineSegment(),
                                SymbolSegment(raw=";", type="symbol", name="semicolon"),
                            ],
                        )
                    ]

                return LintResult(
                    anchor=anchor_segment,
                    fixes=fixes,
                )

        return None

"""Implementation of Rule L058."""

from apm import AllOf, Check, match, Pattern, Some
from apm.core import MatchContext, MatchResult, Nested

from sqlfluff.core.rules.base import BaseRule, LintFix, LintResult, RuleContext
from sqlfluff.core.rules.doc_decorators import document_fix_compatible
from sqlfluff.core.rules.functional import Segments, sp


@document_fix_compatible
class Rule_L058(BaseRule):
    """Nested CASE statements could be flattened.

    | **Anti-pattern**
    | In this example, the outer CASE's "ELSE" is another CASE.

    .. code-block:: sql

        SELECT
          CASE
            WHEN species = 'Cat' THEN 'Meow'
            ELSE
            CASE
               WHEN species = 'Dog' THEN 'Woof'
            END
          END as sound
        FROM mytable

    | **Best practice**
    | Move the body of the inner "CASE" to the end of the outer one.

    .. code-block:: sql

        SELECT
          CASE
            WHEN species = 'Cat' THEN 'Meow'
            WHEN species = 'Dog' THEN 'Woof'
          END AS sound
        FROM mytable

    """

    def _eval(self, context: RuleContext) -> LintResult:
        """Nested CASE should be simplified."""
        segment = context.functional.segment
        if segment.all(sp.is_type("case_expression")):
            children = segment.children()

            # Search for occurrences of the pattern: WHEN <<expression>> ELSE CASE <<expression>>
            matched = MatchResult(matches=True, context=None, match_stack=None)
            while matched:
                matched = match(
                    children,
                    [
                        # ELSE <<expression>>
                        Some(Check(sp.not_(sp.is_type("else_clause")))),
                        "else_clause"
                        @ AllOf(
                            Check(sp.is_type("else_clause")),
                            Attr(
                                "segments",
                                [
                                    "else" @ Check(sp.is_keyword("else")),
                                    Some(Check(sp.not_(sp.is_type("expression")))),
                                    "nested_expression"
                                    @ Attr(
                                        "segments",
                                        [
                                            # case_expression
                                            "nested_case_expression"
                                            @ Check(sp.is_type("case_expression"))
                                        ],
                                    ),
                                    Some(Check(sp.not_(sp.is_keyword("end")))),
                                ],
                            ),
                        ),
                        "junk_before_end" @ Some(Check(sp.not_(sp.is_keyword("end")))),
                        Check(sp.is_keyword("end")),
                    ],
                )
                if matched:
                    fixes = (
                        [
                            # Replace outer ELSE with inner CASE body
                            LintFix.replace(
                                matched["else"],
                                self._to_keep_from_nested_case(matched),
                            ),
                            # Delete inner CASE
                            LintFix.delete(matched["nested_expression"]),
                        ]
                        # Delete stuff from the end of the outer CASE
                        + [
                            LintFix.delete(seg)
                            for seg in Segments(*matched["junk_before_end"]).select(
                                sp.not_(sp.is_meta())
                            )
                        ]
                    )
                    return LintResult(anchor=matched["nested_expression"], fixes=fixes)
        return LintResult()

    @staticmethod
    def _to_keep_from_nested_case(matched):
        """Determine what to keep from the nested CASE."""
        nested_case_children = Segments(*matched["nested_case_expression"].segments)
        # First pass: From the first when_clause (inclusive) to the END
        # (excluding the END).
        start_seg = (
            nested_case_children.select(loop_while=sp.not_(sp.is_type("when_clause")))
            .last()
            .get()
        )
        stop_seg = nested_case_children.last(sp.is_keyword("end")).get()
        to_keep = nested_case_children.select(
            start_seg=start_seg,
            stop_seg=stop_seg,
        )
        # Find any trailing "non-code", and omit it from the stuff to keep.
        trailing_non_code = (
            to_keep.reversed().select(loop_while=sp.not_(sp.is_code())).reversed()
        )
        return to_keep[: -len(trailing_non_code)]

[barrywhart]

it might make sense to extract some common patterns as described in the short paragraph about extensibility in the README: https://github.com/scravy/awesome-pattern-matching#extensible – basically a Check(sp.is_keyword(...)) could be Keyword("when")

About this, yes, we'll think about it. This raises an interesting design question, because we'll need to do similar things in 3 contexts:

• The linter uses a custom parser with a grammar for each dialect of SQL. This code uses classes with similar names as those in awesome-pattern-matching.
• Some rules are implemented using a functional API that uses the same functions like sp.is_keyword().
• Some rules will be implemented using awesome-pattern-matching.

So we'll need to consider the pros, cons, and effort involved in streamlining each of these use cases. Depending on the choices we make, the three may be more or less similar. I hope that makes sense. 😛

[scravy]

Thank you for sharing. It's great to see how apm is being used.

I just released 0.24.1 which has the changes for Some included.