NNNN-swift-predicates.md

Swift Predicates

• Proposal: FOU-NNNN
• Authors: Debbie Goldsmith, Jeremy Schonfeld
• Status: Pitch
• Related Pitches:
  • Expression macros
  • Parameter packs

Revision history

• v1 Initial version
• v2 Added full operator definitions, renamed #predicate to #Predicate, substitute the build_KeyPath function for previous uses of dynamic member lookup

Introduction

A predicate is a construct that performs a true/false test on a provided set of input values. It is very common for developers to need to construct predicates that can be sent across concurrency and process boundaries for later evaluation. Additionally, predicates are commonly converted to external formats such as SQL and other query languages for native evaluation in databases. We would like to introduce new API as part of the FoundationEssentials package to improve the experience of creating, analyzing, and evaluating predicates in Swift.

Swift-evolution thread: Swift Predicates

Motivation

Predicates are already used to pass a filter across software boundaries: through an API, to another process, or across the network. Apple platforms currently use NSPredicate for this purpose, but it has some deficiencies:

1. It isn't type safe
2. It doesn't work with autocomplete in an IDE
3. It has its own syntax, different from Swift
4. It isn't extensible to new expressions or types
5. It is difficult to parse

For example, here's a typical code snippet demonstrating NSPredicate creation and evaluation:

let predicate = NSPredicate(format: "content.length < %@ AND sender.firstName == \"Jeremy\"", NSNumber(280))
if predicate.evaluate(with: message) {
	// ...
}

If the message object is of a type that doesn't have the correct members, the compiler does not provide any warning, and the code fails at run time.

Proposed solution

We propose creating a new value type, Predicate that addresses these problems, as part of the FoundationEssentials package. These new constructions of predicates will be expressed using standard Swift syntax elements and are fully type-checked by the compiler. This allows us to design Predicate to be type safe, readily archivable and Sendable, and integrated with Swift development environments.

Below is the same example as the above NSPredicate construction, but using the proposed Predicate type instead:

let limit = 280
let myPredicate = #Predicate<Message> {
    $0.content.count < limit && $0.sender.firstName == "Jeremy"
}
if try myPredicate.evaluate(message) { ... }

The type of the input arguments is specified via the generic parameter — <Message> here — and they are represented by arguments provided to the closure which will be bound to the actual value when the predicate is evaluated.

Expression closures can also be nested. With NSPredicate, this composition might have looked like the following:

NSPredicate(format: "SUBQUERY(recipients, $recipient, recipient.firstName == sender.firstName").@count > 0")

Predicate instead uses standard Swift syntax: a natural nested closure to capture the subexpression.

let myPredicate = #Predicate<Message> { message in
    message.recipients.filter {
        $0.firstName == message.sender.firstName
    }.count > 0
}

Note that in this example we need to use an explicit closure argument since message is referenced inside the nested closure. The same predicate could be expressed more naturally as:

let myPredicate = #Predicate<Message> { message in
    message.recipients.contains {
        $0.firstName == message.sender.firstName
    }
}

Predicate also conforms to Codable and Sendable so that it can be archived (and shared between processes via XPC) as well as easily passed between concurrency domains. We are designing our approach to allow this to be done with security in mind. Specific details on how Predicate will be securely Codable and the specifics for its archiving design will be addressed in a future proposal.

Detailed design

Proposed API

Expressions

We propose a new PredicateExpression protocol representing a component of a predicate's tree of expressions. Typically these are value types nested within the PredicateExpressions namespace (a caseless, frozen enum). Concrete types conforming to PredicateExpression will also provide builder functions to be invoked by the macro facility (discussed in more detail below). We also define StandardPredicateExpression, a protocol for expressions that are supported by the standard Predicate type (discussed below). Finally, the PredicateError type will describe errors that can be thrown during predicate in-memory evaluation.

@frozen @_nonSendable public enum PredicateExpressions {}

public protocol PredicateExpression<Output> {
    associatedtype Output
    
    func evaluate(_ bindings: PredicateBindings) throws -> Output
}

// Only expressions supported by Predicate itself should conform to this protocol
public protocol StandardPredicateExpression<Output> : PredicateExpression, Codable, Sendable {}

Variables and constants

These concrete expression types are the basic elements of every predicate expression tree: expressions representing a provided input (a variable), a constant value, and a key path rooted from an expression.

extension PredicateExpressions {
    public struct VariableID: Hashable, Codable, Sendable {
    }

    public struct Variable<Output> : StandardPredicateExpression {
        public let key: VariableID
        
        public init()
    }
    
    public struct KeyPath<Root : PredicateExpression, Output> : PredicateExpression {
        public let root: Root
        public let keyPath: Swift.KeyPath<Root.Output, Output> & Sendable
        
        public init(root: Root, keyPath: Swift.KeyPath<Root.Output, Output> & Sendable)
    }

    public struct Value<Output> : PredicateExpression {
        public let value: Output
        
        public init(_ value: Output)
    }
    
    public static func build_Arg<T>(_ arg: T) -> Value<T>
    
    public static func build_Arg<T: PredicateExpression>(_ arg: T) -> T
    
    public static func build_KeyPath<Root, Value>(root: Root, keyPath: Swift.KeyPath<Root.Output, Value>) -> PredicateExpressions.KeyPath<Root, Value>
}

extension PredicateExpressions.KeyPath : StandardPredicateExpression where Root : StandardPredicateExpression {}
extension PredicateExpressions.KeyPath : Codable where Root : Codable {}
extension PredicateExpressions.KeyPath : Sendable where Root : Sendable {}
extension PredicateExpressions.Value : StandardPredicateExpression where Output : Codable & Sendable {}
extension PredicateExpressions.Value : Codable where Output : Codable {}
extension PredicateExpressions.Value : Sendable where Output : Sendable {}

Predicate

We propose the following Predicate type for use as the currency type representing all basic predicates. This predicate supports all standard expressions supported by the Swift language or declared in the standard library. Developers who wish to allow creation of predicates with custom operators (or a restricted subset of these operators) should create their own predicate type to constrain the provided expression type (details provided below). Additionally, we will declare a PredicateError type to represent errors that can be thrown during predicate evaluation as well as a convenience filter(_:) function to filter elements of a sequence based on a predicate.

public struct Predicate<Input...> : Codable, Sendable {
    public let expression: any StandardPredicateExpression<Bool>
    public let variables: (PredicateExpressions.Variable<Input>...)
    
    public init<E: StandardPredicateExpression<Bool>>(_ builder: (PredicateExpressions.Variable<Input>...) -> E)
    
    public func evaluate(_ input: Input...) throws -> Bool
}

public struct PredicateError: Error, Hashable, CustomDebugStringConvertible {
    public static let undefinedVariable: PredicateError
    public static let forceUnwrapFailure: PredicateError
    public static let forceCastFailure: PredicateError
}

extension Sequence {
    public func filter(_ predicate: Predicate<Element>) throws -> [Element]
}

Type-safe variable binding

We will declare a PredicateBindings type to represent a heterogeneous dictionary created during predicate evaluation that maps input variables to their provided constant values.

@_nonSendable
public struct PredicateBindings {
    public init<T...>(_ values: (PredicateExpressions.Variable<T>, T)...)
    
    public subscript<T>(_ variable: PredicateExpressions.Variable<T>) -> T? { get set }
    public func binding<T>(_ variable: PredicateExpressions.Variable<T>, to value: T) -> Self
}

Macro processing

By themselves, the PredicateExpression types don't allow the expressive syntax seen in the "Proposed solution" section above. Swift Predicates take advantage of the new Swift syntactic macro facility, using rewriting rules. Taking the same example, this:

let limit = 280
let myPredicate = #Predicate<Message> {
    $0.content.count < limit && $0.sender.firstName == "Jeremy"
}

would be rewritten into:

let limit = 280
let myPredicate = Predicate<Message> {
	PredicateExpressions.build_Conjunction(
		lhs: PredicateExpressions.build_Arg(
			PredicateExpressions.build_Comparison(
				lhs: PredicateExpressions.build_Arg(
					PredicateExpressions.build_KeyPath(
						root: PredicateExpressions.build_KeyPath(
							root: $0,
							keyPath: \.content
						),
						keyPath: \.count
					)
				),
				rhs: PredicateExpressions.build_Arg(limit),
				op: .lessThan
			)
		),
		rhs: PredicateExpressions.build_Arg(
			PredicateExpressions.build_Equal(
				lhs: PredicateExpressions.build_Arg(
					PredicateExpressions.build_KeyPath(
						root: PredicateExpressions.build_KeyPath(
							root: $0,
							keyPath: \.sender
						),
						keyPath: \.firstName
					)
				),
				rhs: PredicateExpressions.build_Arg("Jeremy")
			)
		)
	)
}

To allow this, we will be defining the following macro that will be included in the swift toolchain.

Note: The PredicateMacro type is not API that will be available at runtime, but rather a macro declaration used by the compiler at compile time.

// Within Foundation
macro Predicate<Input...>(_ body: (Input...) -> Bool) -> Predicate<Input...> = #externalMacro(module: "FoundationMacros", struct: "PredicateMacro")

// Within a new Foundation macros module
public struct PredicateMacro: ExpressionMacro {
	public static func expansion(of node: MacroExpansionExprSyntax, in context: inout MacroExpansionContext) -> ExprSyntax
}

The macro has the capability to transform the expression into calls to builder functions (transformations for all expressions supported by Predicate are listed below). Additionally, the macro will produce compiler errors for any unexpected expression types with clear and easy to read diagnostics for unsupported expressions (such as unknown operators or function calls).

We are working with the Swift team to update naming conventions for macros.

Usage considerations

Predicate Parameterization & Composition

Predicates typically have at least one input, the value being tested; this value is referenced via an argument to the closure that constructs a predicate. Constant values can be captured by a predicate with no special treatment. However, it may also be desirable to parameterize a predicate via additional inputs, for example when composing multiple nested predicates together.

Suppose we want to make limit in our first example a variable rather than a constant. This can be done by taking advantage of the new variadic generics feature. The example can then be written as follows:

let myPredicate = #Predicate<Message, Int> { message, limit in
    message.content.count < limit && $0.sender.firstName == "Jeremy"
}
let result = try myPredicate.evaluate(message, 280)

Note that this predicate has the signature Predicate<Message, Int>, but developers may wish to provide this to APIs as a Predicate<Message> given a certain second Int input.

In other circumstances, you may also wish to compose predicates together as pieces. We can take our example above using the filter function and write it into two pieces so that components of the predicate can be reused:

let personMatch = #Predicate<Person, String> { person, name in
	person.firstName == name
}

let myPredicate = #Predicate<Message> { message in
    !message.recipients.filter(personMatch.substitute(message.sender.firstName)).isEmpty
}

In this case, the personMatch predicate is a reusable predicate that can match a Person by their first name and can be referenced via the expression in myPredicate to match messages in which the sender is also a recipient. In this example just like the previous example, we have a Predicate<Person, String> that needs to be passed to an API that accepts a Predicate<Person>. We plan to incorporate a way to enable substitution of input variables in predicates to "reduce" a predicate to a simplified form for passing to other APIs. The substitute(_:) function here is an example of what that might look like, and we'll expand upon the details of exactly how this can be done in a future proposal.

Tree walking

Predicates can support transformation and analysis via tree walking - a method of traversing a predicate's expression tree while optionally producing a transformed output. For example, a client might want to convert a predicate into an NSPredicate for compatibility with other libraries, or convert it into an external format such as a string-based SQL query or a custom database query object.

Developers will implement tree walking by adding requirements to a protocol to which supported operators will provide conformances. For example, a framework like Spotlight might want to create APIs that accept predicates that are converted to some SpotlightQuery object. Spotlight could include API such as the following to do this:

protocol SpotlightPredicateExpression {
    func spotlightQuery() -> SpotlightQuery
}

// Repeated for each supported/convertible operator
extension PredicateExpressions.Equal : SpotlightPredicateExpression where LHS : SpotlightPredicateExpression, RHS : SpotlightPredicateExpression {
    func spotlightQuery() -> SpotlightQuery {
        /* build SpotlightQuery using lhs.spotlightQuery() and rhs.spotlightQuery() */
    }
}

These protocol requirements can use function arguments to pass along any state needed for the traversal and transformation. When a developer creates a protocol like this to perform tree walking to a custom format, they should write their API in such a way that only convertible predicates are accepted. For example, if an API only wishes to accept predicates convertible to a spotlight query, they would use a custom predicate type to represent expressions convertible to such a format (see section below for more details on this). For example, a framework like spotlight that defines conversion to its query format could define some predicate such as the following:

struct SpotlightPredicate<Input...> {
	let expression: any SpotlightPredicateExpression<Bool>
	    
	// ...
	    
	func convertToSpotlightQuery() -> SpotlightQuery {
		return expression.spotlightQuery()
	}
}

In this manner, providing a predicate with operators not supported in the required external format will result in a compilation error. The predicate macro will produce clear diagnostics to help prevent unnoticed conversion issues resulting in errors ocurring at runtime. Note that conversion can still be allowed to fail for other reasons (for example a large expression tree that surpasses a depth limit for a database) if the comparable walking function is made to throw or return an optional value. We hope that this approach will decrease the number of errors that aren't caught statically while still allowing for runtime errors to be thrown when walking if necessary.

Custom predicate types

The standard Predicate type is meant to comprise a defined set of functions over a defined set of types, so that Predicate can be serialized and shared across process boundaries. Clients may have a need for their own custom functions and allowed data types or a requirement for conversion to their own formats; in that case, they should define their own type.

For example, an application similar to Spotlight might want to define a custom set of functions and types tailored for Spotlight queries (queries that can perform efficient text searching/manipulation but that don't support the full range of all operations). Similar to how Predicate restricts its expressions to a StandardPredicateExpression, a SpotlightPredicate might use a SpotlightPredicateExpression protocol which supported expressions can conform to (possibly including expressions that Predicate also supports). In order to initialize a different predicate type such as SpotlightPredicate, the spotlight framework would also need to define a macro (ex. #spotlightPredicate<Input...>).

Details are forthcoming on how to implement custom predicate types using the tools provided by the macro processor used for Predicate. We will also propose APIs that custom predicate types can use to easily (and securely) conform to Codable in a future proposal.

Expressions supported by Predicate

Here are the APIs of the types currently conforming to StandardPredicateExpression. Others may be added based on feedback.

To make (meaningful) tree walking possible, the various types conforming to PredicateExpression must be public, and the properties required to analyze them must be public as well.

Arithmetic (+, -, *)

extension PredicateExpressions {
    public enum ArithmeticOperator: Codable, Sendable {
        case add, subtract, multiply
    }
    
    public struct Arithmetic<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : Numeric
    {
        public typealias Output = LHS.Output
        
        public let op: ArithmeticOperator
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS, op: ArithmeticOperator)
    }
    
    public static func build_Arithmetic<LHS, RHS>(lhs: LHS, rhs: RHS, op: ArithmeticOperator) -> Arithmetic<LHS, RHS>
}

extension PredicateExpressions.Arithmetic : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Arithmetic : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Arithmetic : Sendable where LHS : Sendable, RHS : Sendable {}

Closed range (...)

extension PredicateExpressions {
    public struct ClosedRange<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output: Comparable
    {
        public typealias Output = Swift.ClosedRange<LHS.Output>
        
        public let lower: LHS
        public let upper: RHS
        
        public init(lower: LHS, upper: RHS)
    }
    
    public static func build_ClosedRange<LHS, RHS>(lower: LHS, upper: RHS) -> ClosedRange<LHS, RHS>
}

extension PredicateExpressions.ClosedRange : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.ClosedRange : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.ClosedRange : Sendable where LHS : Sendable, RHS : Sendable {}

Comparison (<, <=, >, >=)

extension PredicateExpressions {
    public enum ComparisonOperator: Codable, Sendable {
        case lessThan, lessThanOrEqual, greaterThan, greaterThanOrEqual
    }

    public struct Comparison<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : Comparable
    {
        public typealias Output = Bool
        
        public let op: ComparisonOperator

        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS, op: ComparisonOperator)
	}
    
    public static func build_Comparison<LHS, RHS>(lhs: LHS, rhs: RHS, op: ComparisonOperator) -> Comparison<LHS, RHS>
}

extension PredicateExpressions.Comparison : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Comparison : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Comparison : Sendable where LHS : Sendable, RHS : Sendable {}

Conditional (?:)

extension PredicateExpressions {
    public struct Conditional<
        Test : PredicateExpression,
        If : PredicateExpression,
        Else : PredicateExpression
    > : PredicateExpression
    where
    Test.Output == Bool,
    If.Output == Else.Output
    {
        public typealias Output = If.Output
        
        public let test : Test
        public let trueBranch : If
        public let falseBranch : Else
        
        public init(test: Test, trueBranch: If, falseBranch: Else)
    }
    
    public static func build_Conditional<Test, If, Else>(_ test: Test, _ trueBranch: If, _ falseBranch: Else) -> Conditional<Test, If, Else>
}

extension PredicateExpressions.Conditional : StandardPredicateExpression where Test : StandardPredicateExpression, If : StandardPredicateExpression, Else : StandardPredicateExpression {}
extension PredicateExpressions.Conditional : Codable where Test : Codable, If : Codable, Else : Codable {}
extension PredicateExpressions.Conditional : Sendable where Test : Sendable, If : Sendable, Else : Sendable {}

Conjunction (&&)

extension PredicateExpressions {
    public struct Conjunction<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == Bool,
        RHS.Output == Bool
    {
        public typealias Output = Bool
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }
    
    public static func build_Conjunction<LHS, RHS>(lhs: LHS, rhs: RHS) -> Conjunction<LHS, RHS>
}

extension PredicateExpressions.Conjunction : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Conjunction : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Conjunction : Sendable where LHS : Sendable, RHS : Sendable {}

Disjunction (||)

extension PredicateExpressions {
    public struct Disjunction<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == Bool,
        RHS.Output == Bool
    {
        public typealias Output = Bool
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }
    
    public static func build_Disjunction<LHS, RHS>(lhs: LHS, rhs: RHS) -> Disjunction<LHS, RHS>
}

extension PredicateExpressions.Disjunction : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Disjunction : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Disjunction : Sendable where LHS : Sendable, RHS : Sendable {}

Division (/, %)

extension PredicateExpressions {
    public struct IntDivision<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : BinaryInteger
    {
        public typealias Output = LHS.Output
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }

    public struct IntRemainder<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : BinaryInteger
    {
        public typealias Output = LHS.Output
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }

    public struct FloatDivision<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : FloatingPoint
    {
        public typealias Output = LHS.Output
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }
    
    public static func build_Division<LHS, RHS>(lhs: LHS, rhs: RHS) -> IntDivision<LHS, RHS>
    
    public static func build_Division<LHS, RHS>(lhs: LHS, rhs: RHS) -> FloatDivision<LHS, RHS>
    
    public static func build_Remainder<LHS, RHS>(lhs: LHS, rhs: RHS) -> IntRemainder<LHS, RHS>
}

extension PredicateExpressions.FloatDivision : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.IntRemainder : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.IntDivision : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.FloatDivision : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.IntRemainder : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.IntDivision : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.FloatDivision : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.IntRemainder : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.IntDivision : Sendable where LHS : Sendable, RHS : Sendable {}

Equality (==)

extension PredicateExpressions {
    public struct Equal<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : Equatable
    {
        public typealias Output = Bool
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }
    
    public static func build_Equal<LHS, RHS>(lhs: LHS, rhs: RHS) -> Equal<LHS, RHS>
}

extension PredicateExpressions.Equal : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Equal : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Equal : Sendable where LHS : Sendable, RHS : Sendable {}

Filter (.filter())

extension PredicateExpressions {
    public struct Filter<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output: Sequence,
        RHS.Output == Bool
    {
        public typealias Element = LHS.Output.Element
        public typealias Output = [Element]
        
        public let sequence: LHS
        public let filter: RHS
        public let variable: Variable<Element>
        
        public init(_ sequence: LHS, _ builder: (Variable<Element>) -> RHS)
    }
    
    public static func build_filter<LHS, RHS>(_ lhs: LHS, _ builder: (Variable<LHS.Output.Element>) -> RHS) -> Filter<LHS, RHS>
}

extension PredicateExpressions.Filter : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Filter : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Filter : Sendable where LHS : Sendable, RHS : Sendable {}

Inequality (!=)

extension PredicateExpressions {
    public struct NotEqual<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output : Equatable
    {
        public typealias Output = Bool
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }

    public static func build_NotEqual<LHS, RHS>(lhs: LHS, rhs: RHS) -> NotEqual<LHS, RHS>
}

extension PredicateExpressions.NotEqual : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.NotEqual : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.NotEqual : Sendable where LHS : Sendable, RHS : Sendable {}

Negation (!)

extension PredicateExpressions {
    public struct Negation<Wrapped: PredicateExpression> : PredicateExpression where Wrapped.Output == Bool {
        public typealias Output = Bool
        
        public let wrapped: Wrapped
        
        public init(_ wrapped: Wrapped)
    }
    
    public static func build_Negation<T>(_ wrapped: T) -> Negation<T>
}

extension PredicateExpressions.Negation : StandardPredicateExpression where Wrapped : StandardPredicateExpression {}
extension PredicateExpressions.Negation : Codable where Wrapped : Codable {}
extension PredicateExpressions.Negation : Sendable where Wrapped : Sendable {}

Optional (?, ??, !)

extension PredicateExpressions {
    public struct OptionalFlatMap<
        LHS : PredicateExpression,
        Wrapped,
        RHS : PredicateExpression,
        Result
    > : PredicateExpression
    where
    LHS.Output == Optional<Wrapped>
    {
        public typealias Output = Optional<Result>

        public let wrapped: LHS
        public let transform: RHS
        public let variable: Variable<Wrapped>

        public init(_ wrapped: LHS, _ builder: (Variable<Wrapped>) -> RHS) where RHS.Output == Result
        
        public init(_ wrapped: LHS, _ builder: (Variable<Wrapped>) -> RHS) where RHS.Output == Optional<Result>
    }

    public static func build_flatMap<LHS, RHS, Wrapped, Result>(_ wrapped: LHS, _ builder: (Variable<Wrapped>) -> RHS) -> OptionalFlatMap<LHS, Wrapped, RHS, Result> where RHS.Output == Result

    public static func build_flatMap<LHS, RHS, Wrapped, Result>(_ wrapped: LHS, _ builder: (Variable<Wrapped>) -> RHS) -> OptionalFlatMap<LHS, Wrapped, RHS, Result> where RHS.Output == Optional<Result>
    
    public struct NilCoalesce<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
    LHS.Output == Optional<RHS.Output>
    {
        public typealias Output = RHS.Output
        
        public let lhs: LHS
        public let rhs: RHS
        
        public init(lhs: LHS, rhs: RHS)
    }
    
    public static func build_NilCoalesce<LHS, RHS>(lhs: LHS, rhs: RHS) -> NilCoalesce<LHS, RHS>

    public struct ForcedUnwrap<
        LHS : PredicateExpression,
        Wrapped
    > : PredicateExpression
    where
    LHS.Output == Optional<Wrapped>
    {
        public typealias Output = Wrapped
        
        public let lhs: LHS
        
        public init(lhs: LHS)
    }
    
    public static func build_ForcedUnwrap<LHS, Wrapped>(lhs: LHS) -> ForcedUnwrap<LHS, Wrapped> where LHS.Output == Optional<Wrapped>
}

extension PredicateExpressions.OptionalFlatMap : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.NilCoalesce : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.ForcedUnwrap : StandardPredicateExpression where LHS : StandardPredicateExpression {}
extension PredicateExpressions.OptionalFlatMap : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.NilCoalesce : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.ForcedUnwrap : Codable where LHS : Codable {}
extension PredicateExpressions.OptionalFlatMap : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.NilCoalesce : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.ForcedUnwrap : Sendable where LHS : Sendable {}

Range (..<)

extension PredicateExpressions {
    public struct Range<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output == RHS.Output,
        LHS.Output: Comparable
    {
        public typealias Output = Swift.Range<LHS.Output>
        
        public let lower: LHS
        public let upper: RHS
        
        public init(lower: LHS, upper: RHS)
    }
    
    public static func build_Range<LHS, RHS>(lower: LHS, upper: RHS) -> Range<LHS, RHS>
}

extension PredicateExpressions.Range : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.Range : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.Range : Sendable where LHS : Sendable, RHS : Sendable {}

Sequence operations

extension PredicateExpressions {
    public struct SequenceContains<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output : Sequence,
        LHS.Output.Element : Equatable,
        RHS.Output == LHS.Output.Element
    {
        public typealias Output = Bool
        
        public let sequence: LHS
        public let element: RHS
        
        public init(sequence: LHS, element: RHS)
    }
    
    public struct SequenceContainsWhere<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output : Sequence,
        RHS.Output == Bool
    {
        public typealias Element = LHS.Output.Element
        public typealias Output = Bool

        public let sequence: LHS
        public let test: RHS
        public let variable: Variable<Element>
        
        public init(_ sequence: LHS, builder: (Variable<Element>) -> RHS)
    }
    
    public struct SequenceAllSatisfy<
        LHS : PredicateExpression,
        RHS : PredicateExpression
    > : PredicateExpression
    where
        LHS.Output : Sequence,
        RHS.Output == Bool
    {
        public typealias Element = LHS.Output.Element
        public typealias Output = Bool

        public let sequence: LHS
        public let test: RHS
        public let variable: Variable<Element>
        
        public init(_ sequence: LHS, builder: (Variable<Element>) -> RHS)
    }
    
    public static func build_contains<LHS, RHS>(_ lhs: LHS, _ rhs: RHS) -> SequenceContains<LHS, RHS>
    
    public static func build_contains<LHS, RHS>(_ lhs: LHS, where builder: (Variable<LHS.Output.Element>) -> RHS)
    
    public static func build_allSatisfy<LHS, RHS>(_ lhs: LHS, _ builder: (Variable<LHS.Output.Element>) -> RHS) -> SequenceAllSatisfy<LHS, RHS>
}

extension PredicateExpressions.SequenceContains : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.SequenceContainsWhere : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.SequenceAllSatisfy : StandardPredicateExpression where LHS : StandardPredicateExpression, RHS : StandardPredicateExpression {}
extension PredicateExpressions.SequenceContains : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.SequenceContainsWhere : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.SequenceAllSatisfy : Codable where LHS : Codable, RHS : Codable {}
extension PredicateExpressions.SequenceContains : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.SequenceContainsWhere : Sendable where LHS : Sendable, RHS : Sendable {}
extension PredicateExpressions.SequenceAllSatisfy : Sendable where LHS : Sendable, RHS : Sendable {}

Types (as?, as!, is)

extension PredicateExpressions {
    public struct ConditionalCast<
        Input : PredicateExpression,
        Desired
    > : PredicateExpression
    {
        public typealias Output = Optional<Desired>
        public let input: Input
        
        public init(_ input: Input)
    }
    
    public struct ForceCast<
        Input : PredicateExpression,
        Desired
    > : PredicateExpression
    {
        public typealias Output = Desired
        public let input: Input
        
        public init(_ input: Input)
    
    public struct TypeCheck<
        Input : PredicateExpression,
        Desired
    > : PredicateExpression
    {
        public typealias Output = Bool
        public let input: Input
        
        public init(_ input: Input)
    }
}

extension PredicateExpressions.ConditionalCast : StandardPredicateExpression where Input : StandardPredicateExpression {}
extension PredicateExpressions.ForceCast : StandardPredicateExpression where Input : StandardPredicateExpression {}
extension PredicateExpressions.TypeCheck : StandardPredicateExpression where Input : StandardPredicateExpression {}
extension PredicateExpressions.ConditionalCast : Codable where Input : Codable {}
extension PredicateExpressions.ForceCast : Codable where Input : Codable {}
extension PredicateExpressions.TypeCheck : Codable where Input : Codable {}
extension PredicateExpressions.ConditionalCast : Sendable where Input : Sendable {}
extension PredicateExpressions.ForceCast : Sendable where Input : Sendable {}
extension PredicateExpressions.TypeCheck : Sendable where Input : Sendable {}

Unary minus (-)

extension PredicateExpressions {
    public struct UnaryMinus<Wrapped: PredicateExpression> : PredicateExpression where Wrapped.Output: SignedNumeric {
        public typealias Output = Wrapped.Output
        
        public let wrapped: Wrapped
        
        public init(_ wrapped: Wrapped)
    }
    
    public static func build_UnaryMinus<T>(_ inner: T) -> UnaryMinus<T>
}

extension PredicateExpressions.UnaryMinus : StandardPredicateExpression where Wrapped : StandardPredicateExpression {}
extension PredicateExpressions.UnaryMinus : Codable where Wrapped : Codable {}
extension PredicateExpressions.UnaryMinus : Sendable where Wrapped : Sendable {}

Impact on existing code

This is new API that has no effect on existing code.

Alternatives considered

Alternatives to using Macros

We considered a number of alternatives to the current macro approach for the API regarding predicate construction. Many of these proved to have adverse effects on either the API shape or compilation of predicate construction, so we moved forward with the macro approach instead of the approaches listed below.

String-based Syntax

Predicate could use a string (or string interpolation) based syntax similar to NSPredicate rather than using actual Swift syntax. This however has a vast number of drawbacks including lack of support for type safety, autocomplete functionality, and extensibility. Additionally, this syntax can easily become hard to understand and does not fit naturally within Swift code.

DSL Syntax similar to SwiftUI

Predicates could be constructed using a DSL-style syntax that looks similar to SwiftUI's view DSL (using result builders). For example:

let limit = 280
let predicate = Predicate<Message> {
	Conjunction {
		LessThan(\.content.count, limit)
		Equals(\.sender.firstName, "Jeremy")
	}
}

However, this design is not congruent with Swift's use of operators throughout the language since this prefix-based notation of operators is not aligned with Swift's natural use of many infix operators (like == or &&). Additionally, the vertical flow of the result builder here is somewhat undefined and it is unclear what the relationship between multiple expression in the root predicate should be.

Operator Overloading

Additionally, we investigated using operator overloading in order to utilize the native Swift operator syntax during predicate construction. This approach involved adding operator overloads for generic PredicateExpression and the current build functions would also be implemented as extensions on PredicateExpression. This allows for the same syntax we have today for constructing predicates, but it has a handful of drawbacks. First of all, this syntax is somewhat limited in that certain operators such as casting and conditionals cannot be overloaded and would require verbose function-based calls that felt out of place. Additionally, it was easy to fall off of the beaten path and reach an uncanney valley effect when attempting to construct an invalid predicate due to confusing compiler diagnostics. Finally, adding an extremely large API surface of operator overloads leads to exponentially longer build times and we don't feel that these overloads would provide a sustainable solution if added to a commonly imported library and made visible to a large amount of Swift code.

One Predicate Type for All Use Cases

The current design proposes that any developers that need to expand or restrict the set of allowed expressions in their predicate-accepting APIs need to declare their own predicate types with corresponding macros. However, we previously considered only introducing one Predicate type that all clients would use for any use case. However, this approach did not allow developers to specify a set of expected operators within a predicate. We desired this behavior for two main reasons:

1. To allow for static enforcement of supported operators at compile time to avoid accidentally using operators incompatible with the predicate's destination (for example, using a custom operator with an API that can only accept operators it knows how to convert to a specific external format like SQL).
2. To aid with Codable support for predicate so developers can specify exactly which operators (and therefore, which concrete PredicateExpression types) they expect to find in the archive to safely decode predicates.

The most natural way to group operators together into sets is via protocol conformances (for example, the StandardPredicateExpression protocol in this proposal). We attempted to adopt these features with just a singular generic Predicate type, however this required some way to statically associate the Predicate with the operator set's protocol.

To do this we evaluated adding the concrete expression type as a generic type parameter on Predicate (for example, struct Predicate<E: PredicateExpression, Input...>). However, we felt that this unnecessarily complicated the usage of Predicate at most call sites since most APIs only care about what operators are used (the protocol that defines the set of operators) and not what the actual structure of operators are (the concrete type of the expression). Additionally, this makes Predicate fairly unusable with Codable because the Predicate must always be declared statically with its concrete expression type (something that is not possible when decoding an arbitrary predicate from an archive). We were also unable to add the protocol itself as a type parameter of Predicate because using protocols as type parameters is not supported by Swift's generics syntax. We decided to move forward with a version of this idea - the separate predicate types approach - where each framework or use case that defines sets of operators that differ from the set defined by StandardPredicateExpression would declare their own concrete predicate type. Developers can create these types with a simple implementation of the initializer and Codable functions designed specifically with constraints that utilize their version of the StandardPredicateExpression protocol to specify exactly which operators are supported at construction/decoding time.

Conformances to PredicateProtocol

Previously, we also discussed defining a protocol PredicateProtcol that would define the requirements for basic predicate behavior. The requirements would be expression and variables properties, along with an evaluate function. However, we decided to drop this protocol because it did not add much utility to the API. The only place that APIs would use PredicateProtocol were cases where the predicate would always be evaluated in memory and never converted to a different format or encoded. In this case, using a general protocol provided no benefit over pre-existing closures, so we dropped the protocol to simplify the API surface and focus on ensuring the most simple and correct uses of the predicate types were encouraged.