Proposal - Expanding the Swift Overlay [GSoC 2023] [C++ and Swift Interoperability]

Overlay_Expansion_Cxx_Interoperability.md

Overview

At the moment, Swift has some experimental ability to interoperate with C++ by importing a large subset of C++. While the transition towards building a fully functional and highly operable environment to allow C++ APIs to be used from Swift (and vice-versa) has a long way to go, this project's primary goal would be to expand the existing Swift Overlay by further adding more containers from C++, which are widely used in the developer's codebase, while also adding additional functionalities to the individual viable files on the Swift side rather than on C++ side (as reverse-interoperability is out of scope for this project).

C++ Standard Library Containers

There are numerous containers in C++ STL to handle, listed below is the list of types and their respective description -

C++ Standard Library Feature	Brief Description	Operable Status
std::string	Dynamically-allocated Buffer of Characters	Yes
std::vector	Dynamically-allocated Arrays	Yes
std::deque	Vector supporting quick front and back operations	To-Do
std::queue	Standard FIFO Queue	To-Do
std::priority_queue	Heap-based Container (based on Vectors)	To-Do
std::list	Doubly-Linked List supporting constant time operations	To-Do
std::set	Balanced Binary Search Tree (R-B Tree based)	To-Do
std::map	Similar to std::set, behaving like sorted Dictionary	To-Do
std::unordered_map	Hash-Map based Dictionary	To-Do
std::unordered_set	Hash-Map based Set (Unordered)	To-Do

Apart from the Standard Containers as described above, types like std::tuple, std::pair, and various forms of templates could be supported, few examples would be:

• <T, T>
• <T, T, T, T>
• <<T, T>, T>, <T, <T, T>>

(Essentially, commonly used generic-forms could be added as extensions to reduce the workload for developers instead of making their own atleast in case of some basic cases.)

(Although above are some commonly used ones, C++ provides 'Policy Based Data Structures' (aka PBDS) that have high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std, which could also be added to the overlay on the miscellaneous view point of the project.)

Usage and Implementation

The existing files for 'cxx-interop' (in /swift/stdlib/public/Cxx/) have a basic pattern, of implementing their respective 'protocol' conformance and 'extension' with needed visibilities accordingly for the container, i.e., 'Cxx{Container-Name}.swift'.

On a similar fashion, few example functions for std::priority_queue would be:

push(element: T) - Puts an element into the priority queue.
pop() -> T? - Returns and removes the element with the highest (or lowest if ascending) priority or nil if the priority queue is empty.
peek() -> T? - Returns the element with the highest (or lowest if ascending) priority or nil if the priority queue is empty.
clear() - Removes all elements from the priority queue.

#include <algorithm>
#include <vector>
#include <queue>

using P = std::pair<int, int>;
// Creating min-heap priority queue of pairs.
using PQMin = std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>, std::greater<>>;

import CxxTypes
import CxxStdLib

var q = PQMin
while !q.isEmpty {
  // Returns element after popping, this is would be an addition on the Swift side,
  // as currently in similar viable containers in C++, we have to first use .top() and then .pop().
  var cur = q.pop()!
  
  /// do...
}

for x in q {
  print("Element: \(x)")
}

q.clear()

// Potential Example Code for implementation
public protocol CxxPriorityQueue<Element> {
  associatedtype Element
  associatedtype Size: BinaryInteger
  
  func qpop() -> Element? 
}

extension CxxPriorityQueue {
  public func pop() -> Element? {
    return qpop()
  }
}

Performance and Testing

While most of the additions to the overlay shouldn't cause any slow downs or issues during the interoperability, appropriate testing for the container's standard performance could be done, for example, in the above context of heaps (priority queue), all operations must have logarithmic time complexity (~O(log(N)) for a certain input size of elements (N). Tests should be able to ensure any possible errors that could be caused due to corner cases or access of null pointers in certain container types.

Further Improvements and Goals

In the example use case, one could observe the iterations done in this containers using typical 'for in' loops which isn't currently supported in the protocols (ex. CxxSet), this could be definitely be added and reciprocated in the viable containers for better diagnostics and debugging. Currently, automatic conformances aren't provided to the 'CxxSequence', again due to hidden performance downfalls of copying the objects, as 'CxxIterator' needs ownership to prevent object destruction before the last use. There are definitely more improvements and additions which could benefit the overlay on the Swift side, although listing out all of them would be too large for the current context of the project.

Thoughts on C++ and Swift Interoperability

According to my view point and understanding, developers in the near future will benefit alot from this initiative in various ways, whether it is cross-platform or standard dev in Swift, due to the flexibility of using a fast, expressive and memory safe language like Swift and likely cause a switch from C++, whilst having such useful containers with practical deliverable efficiency and have a powerful combination of these languages.

As a discrete example, consider a developer needed a well designed model like Swift for handling OOPs by using protocols, classes, etc. and maybe at a certain point needing something like recursive lambdas (in C++), at the same time passing it as a conversion to its closure form in Swift (possibly). Maybe too futuristic but definitely had this in my mind and shared my thoughts.