Detect circular macro expansion in `MacroSystem`

[ahoppen]

The following recursive expansion of a macro causes an infinite loop in MacroSystem, which is used by assertMacroExpansion. The compiler diagnoses the circular evaluation of the macro. MacroSystem should do the same.

struct InfiniteRecursionMacro: ExpressionMacro {
  static func expansion(of node: some FreestandingMacroExpansionSyntax, in context: some MacroExpansionContext) throws -> ExprSyntax {
    return "#infiniteRecursion"
  }
}

final class MacroSystemTests: XCTestCase {
  func testInfiniteRecursion() {
    assertMacroExpansion("#infiniteRecursion", expandedSource: "", macros: ["infiniteRecursion": InfiniteRecursionMacro.self])
  }
}

[ahoppen]

Tracked in Apple’s issue tracker as rdar://113567654

[AppAppWorks]

How should the circuit breaker be implemented? Would it count on the recursion depth? Or just use a Set to make sure a macro symbol cannot be expanded more than once in the recursion?

[ahoppen]

I would go for the set that ensures we aren’t expanding the same macro twice within the same expansion.

[AppAppWorks]

Working on this issue recently, I've found that it's impossible to detect all circular macro expansions just depending on macro uniqueness, because IIRC Swift Macros are Turing-complete and so the infamous halting problem also applies to macros.

We can assume all freestanding macros are referentially transparent such that identical macros should not be expanded more than once on any expansion path (IIUIC macro expansion performs depth-first search). And by identical I mean equality by description, e.g. #freestanding<Int>(i: 10), because one can always and should be allowed to perform finite recursions with a freestanding macro like this,

private struct InfiniteRecursionMacro: ExpressionMacro {
  static func expansion(
    of node: some FreestandingMacroExpansionSyntax,
    in context: some MacroExpansionContext)
  throws -> ExprSyntax {
    let i = node.arguments.first!.expression.cast(IntegerLiteralExprSyntax.self).representedLiteralValue!
    if i > 0 {
      return "1 + #infiniteRecursion(i: \(raw: i - 1))"
    } else {
      return "0"
    }
  }
}

func testInfiniteRecursion() {
  assertMacroExpansion(
    "#infiniteRecursion(i: 1000)",
    expandedSource: "",
    macros: [
      "infiniteRecursion": InfiniteRecursionMacro.self,
    ]
  )
}

But here the halting problem hits in, what if the macro contains an infinite loop like return "1 + #infiniteRecursion(i: \(raw: i +1))"? It's impossible to tell whether a Turing-complete program will ever halt or not just looking at the macro arguments, and it's non-trivial to statically detect whether the expanded macro will ever halt. Therefore I think we need to introduce another mechanism much akin to the maximum nesting level in Parser to prevent stack overflow from infinite expansion.

Another note is, as reported in #1805, even though SyntaxProtocol.expand() isn't yet a "full" expansion system, the expansion behaviours of different subtypes of AttachedMacro vary as some of them will expand macros recursively to some extent. The behaviour of AttachedMacro by definition depends on its context that most often results in a much more ginormous combinatorial space than the input of a freestanding macro would ever do. Thus it'd be almost impossible to detect circular expansion deterministically without putting a limit to the recursion depth IMO.

[ahoppen]

If you try to compile your #infiniteRecursion macro, you should find that it reports a recursive expansion of the infiniteRecursion. That’s because #infiniteRecursion isn’t allowed to expand to #infiniteRecursion again, even if it contains different argument.

[AppAppWorks]

Does it imply that an expansion path like this should also be prohibited?
#exprMacro1 -> #exprMacro2 -> #exprMacro1?
Such that no two freestanding macro instances of the same type may exist on the same expansion path?

[ahoppen]

Yes, that should also be prohibited.

[AppAppWorks]

Gotcha! My PR will be ready very soon.