Files
Mathias Quintero 6c8ca82973 Improve allocations in Large Field Equality Checks (#150)
### Motivation

Checking for equality of multiple http fields creates an array per field
name. However, not every field will actually have multiple values, which
means we can save array allocations for fields that are only set once.

### Modifications

- Added an enum to handle single values without extra allocations

### Result

Faster equality checks.
2026-09-03 15:00:23 +00:00

516 lines
19 KiB
Swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift open source project
//
// Copyright (c) 2023 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0
//
// See LICENSE.txt for license information
// See CONTRIBUTORS.txt for the list of Swift project authors
//
// SPDX-License-Identifier: Apache-2.0
//
//===----------------------------------------------------------------------===//
/// A collection of HTTP fields. It is used in `HTTPRequest` and `HTTPResponse`, and can also be
/// used as HTTP trailer fields.
///
/// HTTP fields are an ordered list of name-value pairs. Each field is represented as an instance
/// of `HTTPField` struct. `HTTPFields` also offers conveniences to look up fields by their names.
///
/// `HTTPFields` adheres to modern HTTP semantics. In particular, the "Cookie" request header field
/// is split into separate header fields by default.
@available(HTTPTypes 1.0, *)
public struct HTTPFields: Sendable {
/// The fields, in the order they were added.
@usableFromInline
var _fields: [HTTPField] = []
/// Create an empty list of HTTP fields
@inlinable
public init() {}
/// The position of the first field at or after `start` whose canonical name is `name`, or
/// `nil` if there is none.
@inlinable
func firstIndex(ofCanonicalName name: String, from start: [HTTPField].Index = 0) -> Int? {
self._fields[start...].firstIndex(where: { $0.name.canonicalName == name })
}
@inlinable
mutating func append(field: HTTPField) {
precondition(!field.name.isPseudo, "Pseudo header field \"\(field.name)\" disallowed")
self._fields.append(field)
precondition(self._fields.count < UInt16.max, "Too many fields")
}
/// Access the field value string by name.
///
/// Example:
/// ```swift
/// // Set a header field in the request.
/// request.headerFields[.accept] = "*/*"
///
/// // Access a header field value from the response.
/// let contentTypeValue = response.headerFields[.contentType]
/// ```
///
/// If multiple fields with the same name exist, they are concatenated with commas (or
/// semicolons in the case of the "Cookie" header field).
///
/// When setting a "Cookie" header field value, it is split into multiple "Cookie" fields by
/// semicolon.
@inlinable
public subscript(name: HTTPField.Name) -> String? {
get {
let fields = self.fields(for: name)
if fields.first(where: { _ in true }) != nil {
let separator = name == .cookie ? "; " : ", "
return fields.lazy.map { $0.value }.joined(separator: separator)
} else {
return nil
}
}
set {
if let newValue {
#if !hasFeature(Embedded)
if #available(macOS 13.0, iOS 16.0, watchOS 9.0, tvOS 16.0, *),
name == .cookie
{
self.setFields(
newValue.split(separator: "; ", omittingEmptySubsequences: false).lazy.map {
HTTPField(name: name, value: String($0))
},
for: name
)
return
}
#endif
self.setFields(CollectionOfOne(HTTPField(name: name, value: newValue)), for: name)
} else {
self.setFields(EmptyCollection(), for: name)
}
}
}
/// Access the field values by name as an array of strings. The order of fields is preserved.
@inlinable
public subscript(values name: HTTPField.Name) -> [String] {
get {
self.fields(for: name).map { $0.value }
}
set {
self.setFields(newValue.lazy.map { HTTPField(name: name, value: $0) }, for: name)
}
}
/// Access the fields by name as an array. The order of fields is preserved.
@inlinable
public subscript(fields name: HTTPField.Name) -> [HTTPField] {
get {
Array(self.fields(for: name))
}
set {
self.setFields(newValue, for: name)
}
}
@usableFromInline
struct HTTPFieldSequence: Sequence {
@usableFromInline
let fields: HTTPFields
@usableFromInline
let name: HTTPField.Name
@inlinable
init(fields: HTTPFields, name: HTTPField.Name) {
self.fields = fields
self.name = name
}
@usableFromInline
struct Iterator: IteratorProtocol {
@usableFromInline
let fields: HTTPFields
@usableFromInline
let name: HTTPField.Name
/// The position to resume scanning at. Keeping it in the iterator makes reading all
/// the fields with one name a single pass over `fields`.
@usableFromInline
var index: Int
@inlinable
init(fields: HTTPFields, name: HTTPField.Name) {
self.fields = fields
self.name = name
self.index = fields.startIndex
}
@inlinable
mutating func next() -> HTTPField? {
if let index = self.fields.firstIndex(ofCanonicalName: self.name.canonicalName, from: self.index) {
defer { self.index = self.fields.index(after: index) }
return self.fields[index]
}
return nil
}
}
@inlinable
func makeIterator() -> Iterator {
Iterator(fields: self.fields, name: self.name)
}
}
@inlinable
func fields(for name: HTTPField.Name) -> HTTPFieldSequence {
HTTPFieldSequence(fields: self, name: name)
}
@inlinable
mutating func setFields(_ fieldSequence: some Sequence<HTTPField>, for name: HTTPField.Name) {
let canonicalName = name.canonicalName
var existingIndex = self.firstIndex(ofCanonicalName: canonicalName)
var newFieldIterator = fieldSequence.makeIterator()
var toDelete = [Int]()
// A single pass over the fields: the existing fields with this name are overwritten in
// place while new fields last, and the leftovers are collected for removal.
while let index = existingIndex {
if let field = newFieldIterator.next() {
self._fields[index] = field
} else {
toDelete.append(index)
}
existingIndex = self.firstIndex(ofCanonicalName: canonicalName, from: index + 1)
}
if !toDelete.isEmpty {
self._fields.remove(at: toDelete)
}
while let field = newFieldIterator.next() {
self.append(field: field)
}
}
/// Whether one or more field with this name exists in the fields.
/// - Parameter name: The field name.
/// - Returns: Whether a field exists.
@inlinable
public func contains(_ name: HTTPField.Name) -> Bool {
self.firstIndex(ofCanonicalName: name.canonicalName) != nil
}
}
extension HTTPFields: Equatable {
public static func == (lhs: HTTPFields, rhs: HTTPFields) -> Bool {
// Equal means: for every name, the same fields in the same order. Fields with different
// names may be interleaved differently on the two sides.
//
// When checking for equality we try two approaches:
// 1. We walk both fields' elements in lock-step. To support ordering differences within the
// fields, we use `pending` arrays, to store elements that have not appeared in the other.
// This approach is very fast if the two candidates have mostly the same order, however
// if the orders are vastly different, this approach can scale quadratic. Because of this,
// if the `pending` arrays grows too large (>= `maxFieldsToScan`) and there are enough fields
// remaining (>=`minFieldsToIndexByName`), we will stop the lockstep approach and instead
// fallback to:
// 2. An approach in which we build a dictionary from one field list and then remove items
// from it based on the other one. This scales linear but has significant build costs,
// since it needs to hash every field name twice.
if lhs._fields.count != rhs._fields.count {
return false
}
// The index of the fields on either side whose equivalent on the other side has not
// turned up yet. Indexes are stored instead of fields, as this reduces ARC traffic.
// Both arrays remain empty for as long as the two fields hold the same elements in exactly
// the same order. After each iteration both arrays have the same length.
var pendingLeft = [Int]()
var pendingRight = [Int]()
for index in lhs._fields.indices {
// A direct element comparison can only be done if there are no elements in the pending
// arrays. This is to ensure correct ordering. Unpaired elements must be considered
// before the current element.
if pendingLeft.isEmpty {
if lhs._fields[index].name == rhs._fields[index].name {
if lhs._fields[index].value == rhs._fields[index].value {
continue
} else {
// Same name, different value, and no earlier candidate for either of them.
return false
}
} else {
// Disorder starts here
let remaining = lhs._fields.count - index
pendingLeft.reserveCapacity(remaining)
pendingRight.reserveCapacity(remaining)
}
}
let leftName = lhs._fields[index].name
if let match = pendingRight.firstIndex(where: { rhs._fields[$0].name == leftName }) {
// The n-th field of a name pairs only with the other side's n-th field.
if rhs._fields[pendingRight[match]] != lhs._fields[index] {
return false
}
pendingRight.remove(at: match)
} else {
pendingLeft.append(index)
}
let rightName = rhs._fields[index].name
if let match = pendingLeft.firstIndex(where: { lhs._fields[$0].name == rightName }) {
if lhs._fields[pendingLeft[match]] != rhs._fields[index] {
return false
}
pendingLeft.remove(at: match)
} else {
pendingRight.append(index)
}
if pendingLeft.count >= Self.maxPendingFieldsBeforeIndexing,
lhs._fields.count - index >= Self.minFieldsToIndexByName
{
return Self.isEqualByNameIndex(lhs, rhs)
}
}
// Both arrays hold the same count, so empty here means every field found a partner.
return pendingLeft.isEmpty
}
/// How many fields can be unmatched before the lock step walk hands off to
/// ``isEqualByNameIndex(_:_:)``.
private static var maxPendingFieldsBeforeIndexing: Int { 32 }
/// How many fields have to be left for building the index to pay for itself. If
/// `maxPendingFieldsBeforeIndexing` is reached, but there are less than
/// `minFieldsToIndexByName` remaining, the equality check will continue to
/// compare in lock-step.
private static var minFieldsToIndexByName: Int { 64 }
private enum FieldEqualityGroup {
case empty
case single(HTTPField)
case multiple([HTTPField])
mutating func append(_ newElement: HTTPField) {
switch self {
case .empty:
self = .single(newElement)
case .single(let element):
self = .multiple([element, newElement])
case .multiple(var elements):
elements.append(newElement)
self = .multiple(elements)
}
}
mutating func popLast() -> HTTPField? {
switch self {
case .empty:
return nil
case .single(let field):
self = .empty
return field
case .multiple(var fields):
let field = fields.removeLast()
guard let first = fields.first else {
self = .empty
return field
}
if fields.count < 2 {
self = .single(first)
} else {
self = .multiple(fields)
}
return field
}
}
}
/// Answers the same question as `==` in linear time, by indexing `rhs` by name and draining that
/// index while walking `lhs`.
@_spi(HTTPTypesBenchmarking)
public static func isEqualByNameIndex(_ lhs: HTTPFields, _ rhs: HTTPFields) -> Bool {
if lhs._fields.count != rhs._fields.count {
return false
}
// The fields of `rhs`, grouped by name. Fields sharing a name have to appear in the same
// order on both sides. Since we don't want to import swift-collections' Deque, we need
// another way to create a FIFO structure: By adding the fields to the dictionary in reverse
// order, we'll add later values first to the values array. This allows us, when iterating
// the lhs fields, to remove values from the end of the values array.
var remaining = [String: FieldEqualityGroup](minimumCapacity: lhs._fields.count)
for field in rhs._fields.reversed() {
remaining[field.name.canonicalName, default: .empty].append(field)
}
for field in lhs._fields {
guard let group = remaining.index(forKey: field.name.canonicalName),
let candidate = remaining.values[group].popLast()
else {
return false
}
if candidate != field {
return false
}
}
return true
}
}
extension HTTPFields: Hashable {
public func hash(into hasher: inout Hasher) {
// Equality ignores the order of differently named fields, so hashing
// must too. Combine each name's sequence (order of same-named fields
// still matters), then mix those group hashes commutatively.
var grouped = [String: Hasher]()
grouped.reserveCapacity(self._fields.count)
for field in self._fields {
let key = field.name.canonicalName
grouped[key, default: Hasher()].combine(field)
}
var combined = 0
for nameHasher in grouped.values {
// HTTPField already hashes its name, so XOR the per-name sequence hashes directly.
combined ^= nameHasher.finalize()
}
hasher.combine(combined)
hasher.combine(self._fields.count)
}
}
@available(HTTPTypes 1.0, *)
extension HTTPFields: ExpressibleByDictionaryLiteral {
public init(dictionaryLiteral elements: (HTTPField.Name, String)...) {
self.reserveCapacity(elements.count)
for (name, value) in elements {
precondition(!name.isPseudo, "Pseudo header field \"\(name)\" disallowed")
self.append(field: HTTPField(name: name, value: value))
}
precondition(self.count < UInt16.max, "Too many fields")
}
}
@available(HTTPTypes 1.0, *)
extension HTTPFields: RangeReplaceableCollection, RandomAccessCollection, MutableCollection {
public typealias Element = HTTPField
public typealias Index = Int
@inlinable
public var startIndex: Int {
self._fields.startIndex
}
@inlinable
public var endIndex: Int {
self._fields.endIndex
}
@inlinable
public var isEmpty: Bool {
self._fields.isEmpty
}
@inlinable
public subscript(position: Int) -> HTTPField {
get {
guard position >= self.startIndex, position < self.endIndex else {
preconditionFailure("getter position: \(position) out of range in HTTPFields")
}
return self._fields[position]
}
set {
guard position >= self.startIndex, position < self.endIndex else {
preconditionFailure("setter position: \(position) out of range in HTTPFields")
}
if self._fields[position] == newValue {
return
}
if newValue.name != self._fields[position].name {
precondition(!newValue.name.isPseudo, "Pseudo header field \"\(newValue.name)\" disallowed")
}
self._fields[position] = newValue
}
}
public mutating func replaceSubrange<C>(_ subrange: Range<Int>, with newElements: C)
where C: Collection, Element == C.Element {
if subrange.startIndex == self.count {
for field in newElements {
precondition(!field.name.isPseudo, "Pseudo header field \"\(field.name)\" disallowed")
self.append(field: field)
}
} else {
self._fields.replaceSubrange(
subrange,
with: newElements.lazy.map { field in
precondition(!field.name.isPseudo, "Pseudo header field \"\(field.name)\" disallowed")
return field
}
)
precondition(self.count < UInt16.max, "Too many fields")
}
}
public mutating func reserveCapacity(_ capacity: Int) {
self._fields.reserveCapacity(capacity)
}
}
#if !hasFeature(Embedded)
@available(HTTPTypes 1.0, *)
extension HTTPFields: CustomDebugStringConvertible {
public var debugDescription: String {
self._fields.description
}
}
@available(HTTPTypes 1.0, *)
extension HTTPFields: Codable {
public func encode(to encoder: Encoder) throws {
var container = encoder.unkeyedContainer()
try container.encode(contentsOf: self)
}
public init(from decoder: Decoder) throws {
var container = try decoder.unkeyedContainer()
if let count = container.count {
self.reserveCapacity(count)
}
while !container.isAtEnd {
let field = try container.decode(HTTPField.self)
guard !field.name.isPseudo else {
throw DecodingError.dataCorruptedError(
in: container,
debugDescription: "Pseudo header field \"\(field)\" disallowed"
)
}
self.append(field)
}
}
}
#endif
extension Array {
// `removalIndices` must be ordered.
@inlinable
mutating func remove(at removalIndices: some Sequence<Index>) {
var offset = 0
var iterator = removalIndices.makeIterator()
var nextToRemoveOptional = iterator.next()
for index in self.indices {
while let nextToRemove = nextToRemoveOptional, self.index(index, offsetBy: offset) == nextToRemove {
offset += 1
nextToRemoveOptional = iterator.next()
}
let toKeep = self.index(index, offsetBy: offset)
if toKeep < self.endIndex {
self.swapAt(index, toKeep)
} else {
break
}
}
removeLast(offset)
}
}