//===----------------------------------------------------------------------===// // // 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, 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(_ subrange: Range, 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) { 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) } }