Detecting binary operator precedence

Development Source Tooling
1

I'm currently exploring Swift-Syntax by using https://swift-ast-explorer.kishikawakatsumi.com as a playground.

One thing that got me confused is that apparently there's no way to get the left and right expressions of a binary operator. For example:

if number + 1 == 2 { }

Screen Shot 2020-02-02 at 2.37.36 AM
Screen Shot 2020-02-02 at 2.37.36 AM546Ă—678 25.1 KB

I also didn't find anything related to that in BinaryOperatorExprSyntax.

However, the AST does group things differently, in a way which makes it possible to know the operators precedence:

      (if_stmt range=[file.swift:2:1 - line:2:34]
        (binary_expr type='Bool' location=file.swift:2:19 range=[file.swift:2:4 - line:2:28] nothrow
          (dot_syntax_call_expr implicit type='(Float, Float) -> Bool' location=file.swift:2:19 range=[file.swift:2:19 - line:2:19] nothrow
            (declref_expr implicit type='(Float.Type) -> (Float, Float) -> Bool' location=file.swift:2:19 range=[file.swift:2:19 - line:2:19] decl=Swift.(file).FloatingPoint extension.== [with (substitution_map generic_signature=<Self where Self : FloatingPoint> (substitution Self -> Float))] function_ref=double)
            (type_expr implicit type='Float.Type' location=file.swift:2:19 range=[file.swift:2:19 - line:2:19] typerepr='Float'))
          (tuple_expr implicit type='(Float, Float)' location=file.swift:2:4 range=[file.swift:2:4 - line:2:28]
            (binary_expr type='Float' location=file.swift:2:15 range=[file.swift:2:4 - line:2:17] nothrow
              (dot_syntax_call_expr implicit type='(Float, Float) -> Float' location=file.swift:2:15 range=[file.swift:2:15 - line:2:15] nothrow
                (declref_expr type='(Float.Type) -> (Float, Float) -> Float' location=file.swift:2:15 range=[file.swift:2:15 - line:2:15] decl=Swift.(file).Float extension.+ function_ref=unapplied)
                (type_expr implicit type='Float.Type' location=file.swift:2:15 range=[file.swift:2:15 - line:2:15] typerepr='Float'))
              (tuple_expr implicit type='(Float, Float)' location=file.swift:2:4 range=[file.swift:2:4 - line:2:17]
                (declref_expr type='Float' location=file.swift:2:4 range=[file.swift:2:4 - line:2:4] decl=file.(file).myFloating@file.swift:1:5 function_ref=unapplied)
                (integer_literal_expr type='Float' location=file.swift:2:17 range=[file.swift:2:17 - line:2:17] value=1 builtin_initializer=Swift.(file).Float extension.init(_builtinIntegerLiteral:) initializer=**NULL**)))
            (member_ref_expr type='Float' location=file.swift:2:28 range=[file.swift:2:22 - line:2:28] decl=Swift.(file).Float extension.nan
              (type_expr type='Float.Type' location=file.swift:2:22 range=[file.swift:2:22 - line:2:22] typerepr='Float'))))
        (brace_stmt range=[file.swift:2:32 - line:2:34])))))

How would I achieve something like this with SwiftSyntax? Thanks!

2

With SwiftSyntax alone, you can't.

Since Swift allows custom operators to be defined with custom precedence and associativity relationships, and since operators can be defined in different modules and then imported (indeed, most operators are defined in the standard library, not built in to the compiler), these relationships can't be resolved at parsing time. When you parse a single source file, it has no knowledge of operators defined in its dependencies, so it can't resolve those.

The output you see from -dump-ast is after semantic analysis—once dependencies have already been loaded. If you run -dump-parse, you'll see what SwiftSyntax essentially gives you:

      (if_stmt range=[<stdin>:1:1 - line:1:22]
        (sequence_expr type='<null>'
          (unresolved_decl_ref_expr type='<null>' name=number function_ref=unapplied)
          (unresolved_decl_ref_expr type='<null>' name=+ function_ref=unapplied)
          (integer_literal_expr type='<null>' value=1 builtin_initializer=**NULL** initializer=**NULL**)
          (unresolved_decl_ref_expr type='<null>' name=== function_ref=unapplied)
          (integer_literal_expr type='<null>' value=2 builtin_initializer=**NULL** initializer=**NULL**))
        (brace_stmt range=[<stdin>:1:20 - line:1:22])))))

Once the compiler has all the information it needs about operators, it "folds" those sequences into expression trees based on precedence/associativity. In swift-format, we wanted to be able to format expressions using that knowledge, so we ported the folding algorithm to Swift: SequenceExprFolding.swift. This takes a flat SequenceExprSyntax and folds it into a tree. The internal nodes are still SequenceExprSyntax, but they have fixed shapes (2 elements for casts and 3 elements for binary expressions).

For the operators themselves, we just hardcoded the pre-defined operators in OperatorContext.swift. If the folding algorithm encounters one that it doesn't recognize, it tries to handle it with a reasonable default (within the compiler, this would be an error). This isn't perfect, but it's the best we can do without importing all the dependencies of the module containing the file being formatted, which is a non-starter. (In the future, we'll let people add frequently used custom operators to their config file.)

At some point we should upstream the sequence folding code to SwiftSyntax so other tools can make use of it more easily. We'd want to make some other enhancements first, like having distinct node types for the cast expression and binary expression nodes, instead of reusing SequenceExprSyntax.

3 Likes
3

Thanks so much for the detailed response and the links - I'll take a look.