[RFC] Typed child positions: `SyntaxLayout`, `SyntaxProperty` and `propertyInParent`

Summary

SyntaxProtocol.keyPathInParent answers "which child of its parent is this node?" with an AnyKeyPath. Getting that key path and comparing it is expensive: every check instantiates and compares key path objects, and the key path literals that back SyntaxNodeStructure.layout (1,824 of them) cost binary size whether or not a client uses them.

This RFC proposes identifying a child by its position in its parent's layout instead. propertyInParent returns an AnySyntaxProperty, the node's position in its parent's layout, which is trivial to produce and to compare, and FunctionDeclSyntax.layout[.name] spells the value to compare it with. SyntaxProperty<Node, Value> carries the node and child types, so a value of it can also read and replace the child it names:

// Is `node` the name of a function declaration?
if node.propertyInParent == FunctionDeclSyntax.layout[.name] { ... }

// Read and replace the child that `side` names.
let side: SyntaxProperty<InfixOperatorExprSyntax, ExprSyntax> = .leftOperand
let operand = infixExpr[property: side]
let replaced = infixExpr.with(side, newOperand)

Inside swift-syntax package, every use of keyPathInParent and SyntaxProtocol.structure moves to the new API. Both stay as they are in this proposal; the intent is to deprecate them eventually, with propertyInParent replacing keyPathInParent.

Measured with a recent Swift 6.5 compiler, BasicFormat (formatted() on a 468 KB and a 178 KB file, parsed and with trivia stripped) executes 23%–26% fewer instructions than on main, with byte-identical output.

Link to PR

Swift Interface

New declarations in SwiftSyntax, in three parts: the static properties that name a child, the positions that say which child a node is, and the operations that read and replace a child through either.

Naming a child

/// A child of the syntax node type `Node` whose type is `Value`, e.g.
/// `SyntaxProperty<ReturnStmtSyntax, ExprSyntax?>.expression`.
@frozen
public struct SyntaxProperty<Node: SyntaxProtocol, Value> {}

Generated for each of the 244 layout node types, with one static property per child (1,824 in all), for example:

extension SyntaxProperty where Node == ReturnStmtSyntax {
  @_alwaysEmitIntoClient
  public static var unexpectedBeforeReturnKeyword: SyntaxProperty<Node, UnexpectedNodesSyntax?> { get }
  @_alwaysEmitIntoClient
  public static var returnKeyword: SyntaxProperty<Node, TokenSyntax> { get }
  @_alwaysEmitIntoClient
  public static var unexpectedBetweenReturnKeywordAndExpression: SyntaxProperty<Node, UnexpectedNodesSyntax?> { get }
  @_alwaysEmitIntoClient
  public static var expression: SyntaxProperty<Node, ExprSyntax?> { get }
  @_alwaysEmitIntoClient
  public static var unexpectedAfterExpression: SyntaxProperty<Node, UnexpectedNodesSyntax?> { get }
}

The static properties are emitted into the client, so the library carries none of them; under library evolution that is what @frozen on SyntaxProperty makes possible.

Which child a node is

extension SyntaxProtocol {
  /// The position this node occupies in its parent's layout, or `nil` if this node is
  /// the root or an element of a collection.
  public var propertyInParent: AnySyntaxProperty? { get }
}

/// A child position in the layout of a particular kind of syntax node.
public struct AnySyntaxProperty: Hashable {}

/// The layout of a syntax node type, e.g. `FunctionDeclSyntax.layout`.
@frozen
public struct SyntaxLayout<Node: SyntaxProtocol> {
  /// The position of a child of `Node`, e.g. `FunctionDeclSyntax.layout[.name]`.
  public subscript<T>(property: SyntaxProperty<Node, T>) -> AnySyntaxProperty { get }
}

AnySyntaxProperty is SyntaxProperty with the node and child types erased, as AnyKeyPath is KeyPath with its root and value types erased.

Generated for each layout node type, for example:

extension ReturnStmtSyntax {
  /// The layout of `ReturnStmtSyntax`.
  @_alwaysEmitIntoClient
  public static var layout: SyntaxLayout<Self> { get }
}

Like the static properties that name a child, layout is emitted into the client, and SyntaxLayout is @frozen for the same reason.

Reading and replacing a child

extension SyntaxProtocol {
  /// The child at `property`.
  public subscript<T: SyntaxProtocol>(property property: SyntaxProperty<Self, T>) -> T { get }
  public subscript<T: SyntaxProtocol>(property property: SyntaxProperty<Self, T?>) -> T? { get }

  /// The child at `property`.
  ///
  /// Returns `nil` if `property` is a position in the layout of another kind of node, and
  /// `.some(nil)` if this node has no child at `property`.
  public subscript(property property: AnySyntaxProperty) -> Syntax?? { get }

  /// Returns a copy of this node with the child at `property` replaced by `value`.
  public func with<T: SyntaxProtocol>(_ property: SyntaxProperty<Self, T>, _ value: T) -> Self
  public func with<T: SyntaxProtocol>(_ property: SyntaxProperty<Self, T?>, _ value: T?) -> Self
}

The members taking a SyntaxProperty are for code that holds one as a value; the property: label is the analogue of keyPath:. When the child is known where it is accessed, the node's own property and key paths remain the way to read and replace it: returnStmt.expression and returnStmt.with(\.expression, newExpr) compile to a direct access, while returnStmt[property: .expression] costs a few more instructions.

Unlike AnyKeyPath, whose root must match the static type of the value it is applied to, node[property: position] with an AnySyntaxProperty matches the kind of the node at run time, so it works on a Syntax or any other wrapper of the node. Like the AnyKeyPath subscript, it tells the two ways of not finding a child apart: it returns nil when node is a different kind, and .some(nil) when the child is absent.

Use Cases

Asking which child a node is

This comes up wherever code reacts to context: BasicFormat decides indentation and spacing from it, SyntaxClassifier classifies identifiers by it, and the diagnostics generator names children with it. Tools that walk a tree and need to know where they are, such as formatters, linters and refactorings, have the same need.

Keeping positions as values

An AnySyntaxProperty is a plain Hashable value, so it can be kept and passed around rather than only matched in a switch. A formatter can hold the positions it treats specially in a set:

let indentedChildren: Set<AnySyntaxProperty> = [
  CodeBlockSyntax.layout[.statements],
  MemberBlockSyntax.layout[.members],
  SwitchCaseSyntax.layout[.statements],
]

func isIndented(_ node: some SyntaxProtocol) -> Bool {
  guard let property = node.propertyInParent else { return false }
  return indentedChildren.contains(property)
}

And a node's location can be recorded as the steps from the root, then replayed in another tree, for example to find the node in an edited tree that sits where a node sat in the original. Replaying a step with node[property: property] returns nil rather than trapping when the node at that step is now a different kind; the replay below treats that and an absent child alike:

enum Step: Hashable {
  case child(AnySyntaxProperty)     // a child of a layout node
  case element(Int)                 // an element of a collection
}

func path(to node: some SyntaxProtocol) -> [Step] {
  var steps: [Step] = []
  var node = Syntax(node)
  while let parent = node.parent {
    if let property = node.propertyInParent {
      steps.append(.child(property))
    } else {
      let siblings = parent.children(viewMode: .all)
      steps.append(.element(siblings.distance(from: siblings.startIndex, to: node.index)))
    }
    node = parent
  }
  return steps.reversed()
}

func descendant(at path: [Step], from root: some SyntaxProtocol) -> Syntax? {
  var node = Syntax(root)
  for step in path {
    switch step {
    case .child(let property):
      guard let child = node[property: property] ?? nil else { return nil }
      node = child
    case .element(let i):
      let elements = node.children(viewMode: .all)
      guard let index = elements.index(elements.startIndex, offsetBy: i, limitedBy: elements.endIndex),
        index != elements.endIndex
      else { return nil }
      node = elements[index]
    }
  }
  return node
}

Acting on a child through a value

Because a SyntaxProperty both names a position and reads and replaces the child there, one value can find a node's place in its parent and then act on it. A refactoring that parenthesizes whichever operand the cursor is on:

func parenthesizeOperand(at node: some SyntaxProtocol) -> InfixOperatorExprSyntax? {
  guard let infixExpr = node.parent?.as(InfixOperatorExprSyntax.self) else { return nil }
  let sides: [SyntaxProperty<InfixOperatorExprSyntax, ExprSyntax>] = [.leftOperand, .rightOperand]
  guard let side = sides.first(where: { node.propertyInParent == InfixOperatorExprSyntax.layout[$0] }) else {
    return nil
  }
  let operand = infixExpr[property: side]
  return infixExpr.with(side, ExprSyntax(TupleExprSyntax(elements: [LabeledExprSyntax(expression: operand)])))
}

A key path can read and replace a child, but finding which key path a node sits at goes through keyPathInParent, and a key path that is not a literal where it is used is projected through the key path runtime.

Effect on existing API

No existing API changes in this proposal. swift-syntax itself no longer uses keyPathInParent or SyntaxProtocol.structure, and the intent is to deprecate both in a later release, after clients have had time to move to propertyInParent.

Migration from key paths to the new API. Asking which child a node is:

// keyPathInParent
switch node.keyPathInParent {
case \FunctionCallExprSyntax.arguments, \TupleExprSyntax.elements:
  return true
default:
  return false
}

// propertyInParent
switch node.propertyInParent {
case FunctionCallExprSyntax.layout[.arguments], TupleExprSyntax.layout[.elements]:
  return true
default:
  return false
}

Reading and replacing a child needs no migration: keep returnStmt.expression and returnStmt.with(\.expression, newExpr). SyntaxProperty adds a way to do the same through a value, not a replacement for key paths.

Future Directions

Describing a layout's children. SyntaxLayout<Node> could be a collection of Node's children, each element giving the child's AnySyntaxProperty and its type, such as ExprSyntax? for the expression of ReturnStmtSyntax:

for child in ReturnStmtSyntax.layout {
  print(child.property, child.type)
}

This is what SyntaxProtocol.structure describes today, without key paths, so it would give clients that inspect a node's children through structure somewhere to move before structure is deprecated.

Converting back to SyntaxProperty. With each child's type recorded, SyntaxProperty.init?(_: AnySyntaxProperty) could check both the node kind and the child type and return nil if either does not match, as downcasting an AnyKeyPath to a KeyPath does. The same check would make an untyped with(_: AnySyntaxProperty, _: Syntax?) possible, returning nil if the replacement does not fit the position, where without it a mismatched replacement would build an invalid tree.

Both need a table of the 1,824 child types in the library. Though that is much smaller than the key paths behind structure.

This looks really nice! A couple random thoughts:

Having to spell out the full generic signature for the SyntaxProperty type to get access to the property handle in isolation feels awkward, but presumably type inference would let us at least replace the child type with a placeholder since the parent type + property name would uniquely identify it, right? As in, this should be equivalent to what you have in your first example:

let side = SyntaxProperty<InfixOperatorExprSyntax, _>.leftOperand

I've grown less fond of the .with function for doing replacement; since syntax nodes are just value types I prefer to do regular mutation these days instead of with method chains. Does the property subscript have a setter as well?

infixExpr[property: side] = newOperand

You mentioned runtime benchmarks, but do you have any numbers on the impact on build time for swift-syntax with these new properties being generated?

It worked for:

let side: SyntaxProperty<InfixOperatorExprSyntax, _> = .leftOperand

But not for SyntaxProperty<InfixOperatorExprSyntax, _>.leftOperand
So I decided to constrain each generated SyntaxProperty static values with the explicit Node and Value

extension SyntaxProperty<InfixOperatorExprSyntax, ExprSyntax> {
  @_alwaysEmitIntoClient public static var leftOperand: Self { ... }
  @_alwaysEmitIntoClient public static var rightOperand: Self { ... }
}

So the type inference works for both.

1 Like

It didn't, but there's no reason for that. I've added the setter as well.

1 Like

I just measured. The generated properties add about 9–10% to SwiftSyntax's type-checking. The module still builds faster than on main overall, mostly because the key-path-based child-name lookup (childName(_: AnyKeyPath)) it replaces costed more than that to compile.

Instruction counts:

main PR
Debug build of the whole package 949 G instructions 880 G (βˆ’7.3%)
Debug, SwiftSyntax 349 G 284 G (βˆ’18.7%)
Debug, SwiftSyntax type-checking 103 G 113 G (+9.9%)
Debug, SwiftParserDiagnostics (uses layout[...] in a 1,824-case switch) 32.9 G 33.3 G (+1.3%)
Release, SwiftSyntax 1,211 G 1,128 G (βˆ’6.9%)
Release, SwiftSyntax type-checking 65.5 G 71.2 G (+8.7%)

Wall-clock is unchanged within noise.

1 Like

This is a good direction. You've managed to get very close to the ergonomics of key paths while improving performance considerably, which is absolutely worth doing. Thanks for implementing @allevato's ideas around assignment and type inference, too.

Doug

1 Like