Permalink
Switch branches/tags
type-name-lookup-fail swift-DEVELOPMENT-SNAPSHOT-2018-10-03-a swift-DEVELOPMENT-SNAPSHOT-2018-10-02-a swift-DEVELOPMENT-SNAPSHOT-2018-10-01-a swift-DEVELOPMENT-SNAPSHOT-2018-09-28-a swift-DEVELOPMENT-SNAPSHOT-2018-09-27-a swift-DEVELOPMENT-SNAPSHOT-2018-09-22-a swift-DEVELOPMENT-SNAPSHOT-2018-09-21-a swift-DEVELOPMENT-SNAPSHOT-2018-09-20-a swift-DEVELOPMENT-SNAPSHOT-2018-09-19-a swift-DEVELOPMENT-SNAPSHOT-2018-09-18-a swift-DEVELOPMENT-SNAPSHOT-2018-09-14-a swift-DEVELOPMENT-SNAPSHOT-2018-09-13-a swift-DEVELOPMENT-SNAPSHOT-2018-09-10-a swift-DEVELOPMENT-SNAPSHOT-2018-09-08-a swift-DEVELOPMENT-SNAPSHOT-2018-09-07-a swift-DEVELOPMENT-SNAPSHOT-2018-09-04-a swift-DEVELOPMENT-SNAPSHOT-2018-08-25-a swift-DEVELOPMENT-SNAPSHOT-2018-08-24-a swift-DEVELOPMENT-SNAPSHOT-2018-08-23-a swift-DEVELOPMENT-SNAPSHOT-2018-08-22-a swift-DEVELOPMENT-SNAPSHOT-2018-08-21-a swift-DEVELOPMENT-SNAPSHOT-2018-08-20-a swift-DEVELOPMENT-SNAPSHOT-2018-08-18-a swift-DEVELOPMENT-SNAPSHOT-2018-08-16-a swift-DEVELOPMENT-SNAPSHOT-2018-08-15-a swift-DEVELOPMENT-SNAPSHOT-2018-08-14-a swift-DEVELOPMENT-SNAPSHOT-2018-08-10-a swift-DEVELOPMENT-SNAPSHOT-2018-08-09-a swift-DEVELOPMENT-SNAPSHOT-2018-08-06-a swift-DEVELOPMENT-SNAPSHOT-2018-08-02-a swift-DEVELOPMENT-SNAPSHOT-2018-08-01-a swift-DEVELOPMENT-SNAPSHOT-2018-07-31-a swift-DEVELOPMENT-SNAPSHOT-2018-07-30-a swift-DEVELOPMENT-SNAPSHOT-2018-07-28-a swift-DEVELOPMENT-SNAPSHOT-2018-07-27-a swift-DEVELOPMENT-SNAPSHOT-2018-07-24-a swift-DEVELOPMENT-SNAPSHOT-2018-07-23-a swift-DEVELOPMENT-SNAPSHOT-2018-07-22-a swift-DEVELOPMENT-SNAPSHOT-2018-07-21-a swift-DEVELOPMENT-SNAPSHOT-2018-07-20-a swift-DEVELOPMENT-SNAPSHOT-2018-07-19-a swift-DEVELOPMENT-SNAPSHOT-2018-07-18-a swift-DEVELOPMENT-SNAPSHOT-2018-07-17-a swift-DEVELOPMENT-SNAPSHOT-2018-07-16-a swift-DEVELOPMENT-SNAPSHOT-2018-07-14-a swift-DEVELOPMENT-SNAPSHOT-2018-07-13-a swift-DEVELOPMENT-SNAPSHOT-2018-07-12-a swift-DEVELOPMENT-SNAPSHOT-2018-07-11-a swift-DEVELOPMENT-SNAPSHOT-2018-07-09-a swift-DEVELOPMENT-SNAPSHOT-2018-07-07-a swift-DEVELOPMENT-SNAPSHOT-2018-07-06-a swift-DEVELOPMENT-SNAPSHOT-2018-07-05-a swift-DEVELOPMENT-SNAPSHOT-2018-07-04-a swift-DEVELOPMENT-SNAPSHOT-2018-07-03-a swift-DEVELOPMENT-SNAPSHOT-2018-07-02-a swift-DEVELOPMENT-SNAPSHOT-2018-07-01-a swift-DEVELOPMENT-SNAPSHOT-2018-06-30-a swift-DEVELOPMENT-SNAPSHOT-2018-06-29-a swift-DEVELOPMENT-SNAPSHOT-2018-06-27-a swift-DEVELOPMENT-SNAPSHOT-2018-06-26-a swift-DEVELOPMENT-SNAPSHOT-2018-06-25-a swift-DEVELOPMENT-SNAPSHOT-2018-06-24-a swift-DEVELOPMENT-SNAPSHOT-2018-06-23-a swift-DEVELOPMENT-SNAPSHOT-2018-06-22-a swift-DEVELOPMENT-SNAPSHOT-2018-06-21-a swift-DEVELOPMENT-SNAPSHOT-2018-06-20-a swift-DEVELOPMENT-SNAPSHOT-2018-06-19-a swift-DEVELOPMENT-SNAPSHOT-2018-06-18-a swift-DEVELOPMENT-SNAPSHOT-2018-06-17-a swift-DEVELOPMENT-SNAPSHOT-2018-06-16-a swift-DEVELOPMENT-SNAPSHOT-2018-06-15-a swift-DEVELOPMENT-SNAPSHOT-2018-06-14-a swift-DEVELOPMENT-SNAPSHOT-2018-06-08-a swift-DEVELOPMENT-SNAPSHOT-2018-06-07-a swift-DEVELOPMENT-SNAPSHOT-2018-06-06-a swift-DEVELOPMENT-SNAPSHOT-2018-06-05-a swift-DEVELOPMENT-SNAPSHOT-2018-06-04-a swift-DEVELOPMENT-SNAPSHOT-2018-06-03-a swift-DEVELOPMENT-SNAPSHOT-2018-06-02-a swift-DEVELOPMENT-SNAPSHOT-2018-06-01-a swift-DEVELOPMENT-SNAPSHOT-2018-05-31-a swift-DEVELOPMENT-SNAPSHOT-2018-05-30-a swift-DEVELOPMENT-SNAPSHOT-2018-05-29-a swift-DEVELOPMENT-SNAPSHOT-2018-05-28-a swift-DEVELOPMENT-SNAPSHOT-2018-05-27-a swift-DEVELOPMENT-SNAPSHOT-2018-05-26-a swift-DEVELOPMENT-SNAPSHOT-2018-05-25-a swift-DEVELOPMENT-SNAPSHOT-2018-05-24-a swift-DEVELOPMENT-SNAPSHOT-2018-05-23-a swift-DEVELOPMENT-SNAPSHOT-2018-05-22-a swift-DEVELOPMENT-SNAPSHOT-2018-05-21-a swift-DEVELOPMENT-SNAPSHOT-2018-05-20-a swift-DEVELOPMENT-SNAPSHOT-2018-05-19-a swift-DEVELOPMENT-SNAPSHOT-2018-05-18-a swift-DEVELOPMENT-SNAPSHOT-2018-05-17-a swift-DEVELOPMENT-SNAPSHOT-2018-05-14-a swift-DEVELOPMENT-SNAPSHOT-2018-05-13-a swift-DEVELOPMENT-SNAPSHOT-2018-05-11-a swift-DEVELOPMENT-SNAPSHOT-2018-05-10-a
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
420 lines (368 sloc) 12.5 KB
//===--- PatternMatching.swift --------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: %target-run-simple-swift
// REQUIRES: executable_test
//===--- Niceties ---------------------------------------------------------===//
extension Collection {
func index(_ d: Int) -> Index {
return index(startIndex, offsetBy: d)
}
func offset(of i: Index) -> Int {
return distance(from: startIndex, to: i)
}
}
//===--- Niceties ---------------------------------------------------------===//
enum MatchResult<Index: Comparable, MatchData> {
case found(end: Index, data: MatchData)
case notFound(resumeAt: Index?)
}
protocol Pattern {
associatedtype Element : Equatable
associatedtype Index : Comparable
associatedtype MatchData = ()
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, MatchData>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
}
extension Pattern {
func found<C: Collection>(in c: C) -> (extent: Range<Index>, data: MatchData)?
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
var i = c.startIndex
while i != c.endIndex {
let m = self.matched(atStartOf: c[i..<c.endIndex])
switch m {
case .found(let end, let data):
return (extent: i..<end, data: data)
case .notFound(let j):
i = j ?? c.index(after: i)
}
}
return nil
}
}
// FIXME: Using this matcher for found(in:) has worst-case performance
// O(pattern.count * c.count).
//
// Also implement one or more of
// KMP/Boyer-Moore[-Galil]/Sustik-Moore/Z-algorithm which run in O(pattern.count
// + c.count)
struct LiteralMatch<T: Collection, Index: Comparable> : Pattern
where T.Element : Equatable {
typealias Element = T.Element
init(_ pattern: T) { self.pattern = pattern }
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, ()>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
var i = c.startIndex
for p in pattern {
if i == c.endIndex || c[i] != p {
return .notFound(resumeAt: nil)
}
i = c.index(after: i)
}
return .found(end: i, data: ())
}
fileprivate let pattern: T
}
struct MatchAnyOne<T : Equatable, Index : Comparable> : Pattern {
typealias Element = T
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, ()>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
return c.isEmpty
? .notFound(resumeAt: c.endIndex)
: .found(end: c.index(after: c.startIndex), data: ())
}
}
extension MatchAnyOne : CustomStringConvertible {
var description: String { return "." }
}
enum MatchAny {}
var __ : MatchAny.Type { return MatchAny.self }
prefix func % <
T : Equatable, Index : Comparable
>(_: MatchAny.Type) -> MatchAnyOne<T,Index> {
return MatchAnyOne()
}
/// A matcher for two other matchers in sequence.
struct ConsecutiveMatches<M0: Pattern, M1: Pattern> : Pattern
where M0.Element == M1.Element, M0.Index == M1.Index {
init(_ m0: M0, _ m1: M1) { self.matchers = (m0, m1) }
fileprivate let matchers: (M0, M1)
typealias Element = M0.Element
typealias Index = M0.Index
typealias MatchData = (midPoint: M0.Index, data: (M0.MatchData, M1.MatchData))
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, MatchData>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
var src0 = c[c.startIndex..<c.endIndex]
while true {
switch matchers.0.matched(atStartOf: src0) {
case .found(let end0, let data0):
switch matchers.1.matched(atStartOf: c[end0..<c.endIndex]) {
case .found(let end1, let data1):
return .found(end: end1, data: (midPoint: end0, data: (data0, data1)))
case .notFound(_):
if src0.isEmpty {
// I don't think we can know anything interesting about where to
// begin searching again, because there's no communication between
// the two matchers that would allow it.
return .notFound(resumeAt: nil)
}
// backtrack
src0 = src0.dropLast()
}
case .notFound(let j):
return .notFound(resumeAt: j)
}
}
}
}
extension ConsecutiveMatches : CustomStringConvertible {
var description: String { return "(\(matchers.0))(\(matchers.1))" }
}
struct RepeatMatch<M0: Pattern> : Pattern {
typealias Element = M0.Element
typealias MatchData = [(end: M0.Index, data: M0.MatchData)]
let singlePattern: M0
var repeatLimits: ClosedRange<Int>
func matched<C: Collection>(atStartOf c: C) -> MatchResult<M0.Index, MatchData>
where C.Index == M0.Index, C.Element == M0.Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
var lastEnd = c.startIndex
var rest = c.dropFirst(0)
var data: MatchData = []
searchLoop:
while !rest.isEmpty {
switch singlePattern.matched(atStartOf: rest) {
case .found(let x):
data.append(x)
lastEnd = x.end
if data.count == repeatLimits.upperBound { break }
rest = rest[x.end..<rest.endIndex]
case .notFound(let r):
if !repeatLimits.contains(data.count) {
return .notFound(resumeAt: r)
}
break searchLoop
}
}
return .found(end: lastEnd, data: data)
}
}
extension RepeatMatch : CustomStringConvertible {
var description: String {
let suffix: String
switch (repeatLimits.lowerBound, repeatLimits.upperBound) {
case (0, Int.max):
suffix = "*"
case (1, Int.max):
suffix = "+"
case (let l, Int.max):
suffix = "{\(l)...}"
default:
suffix = "\(repeatLimits)"
}
return "(\(singlePattern))\(suffix)"
}
}
enum OneOf<A, B> {
case a(A)
case b(B)
}
extension OneOf : CustomStringConvertible {
var description: String {
switch self {
case .a(let x):
return "\(x)"
case .b(let x):
return "\(x)"
}
}
}
struct MatchOneOf<M0: Pattern, M1: Pattern> : Pattern
where M0.Element == M1.Element, M0.Index == M1.Index {
init(_ m0: M0, _ m1: M1) { self.matchers = (m0, m1) }
fileprivate let matchers: (M0, M1)
typealias Element = M0.Element
typealias Index = M0.Index
typealias MatchData = OneOf<M0.MatchData,M1.MatchData>
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, MatchData>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
switch matchers.0.matched(atStartOf: c) {
case .found(let end, let data):
return .found(end: end, data: .a(data))
case .notFound(let r0):
switch matchers.1.matched(atStartOf: c) {
case .found(let end, let data):
return .found(end: end, data: .b(data))
case .notFound(let r1):
if let s0 = r0, let s1 = r1 {
return .notFound(resumeAt: min(s0, s1))
}
return .notFound(resumeAt: nil)
}
}
}
}
extension MatchOneOf : CustomStringConvertible {
var description: String { return "\(matchers.0)|\(matchers.1)" }
}
infix operator .. : AdditionPrecedence
postfix operator *
postfix operator +
func .. <M0: Pattern, M1: Pattern>(m0: M0, m1: M1) -> ConsecutiveMatches<M0,M1> {
return ConsecutiveMatches(m0, m1)
}
postfix func * <M: Pattern>(m: M) -> RepeatMatch<M> {
return RepeatMatch(singlePattern: m, repeatLimits: 0...Int.max)
}
postfix func + <M: Pattern>(m: M) -> RepeatMatch<M> {
return RepeatMatch(singlePattern: m, repeatLimits: 1...Int.max)
}
func | <M0: Pattern, M1: Pattern>(m0: M0, m1: M1) -> MatchOneOf<M0,M1> {
return MatchOneOf(m0, m1)
}
//===--- Just for testing -------------------------------------------------===//
struct MatchStaticString : Pattern {
typealias Element = UTF8.CodeUnit
typealias Buffer = UnsafeBufferPointer<Element>
typealias Index = Buffer.Index
let content: StaticString
init(_ x: StaticString) { content = x }
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, ()>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
return content.withUTF8Buffer {
LiteralMatch<Buffer, Index>($0).matched(atStartOf: c)
}
}
}
extension MatchStaticString : CustomStringConvertible {
var description: String { return String(describing: content) }
}
// A way to force string literals to be interpreted as StaticString
prefix operator %
extension StaticString {
static prefix func %(x: StaticString) -> MatchStaticString {
return MatchStaticString(x)
}
}
extension Collection where Iterator.Element == UTF8.CodeUnit {
var u8str : String {
var a = Array<UTF8.CodeUnit>()
a.reserveCapacity(numericCast(count) + 1)
a.append(contentsOf: self)
a.append(0)
return String(reflecting: String(cString: a))
}
}
extension Pattern where Element == UTF8.CodeUnit {
func searchTest<C: Collection>(
in c: C,
format: (MatchData)->String = { String(reflecting: $0) })
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection {
print("searching for /\(self)/ in \(c.u8str)...", terminator: "")
if let (extent, data) = self.found(in: c) {
print(
"\nfound at",
"\(c.offset(of: extent.lowerBound)..<c.offset(of: extent.upperBound)):",
c[extent].u8str,
MatchData.self == Void.self ? "" : "\ndata: \(format(data))")
}
else {
print("NOT FOUND")
}
print()
}
}
//===--- Just for testing -------------------------------------------------===//
//===--- Tests ------------------------------------------------------------===//
let source = Array("the quick brown fox jumps over the lazy dog".utf8)
let source2 = Array("hack hack cough cough cough spork".utf8)
(%"fox").searchTest(in: source)
(%"fog").searchTest(in: source)
(%"fox" .. %" box").searchTest(in: source)
(%"fox" .. %" jump").searchTest(in: source)
(%"cough")*.searchTest(in: source2)
(%"sneeze")+.searchTest(in: source2)
(%"hack ")*.searchTest(in: source2)
(%"cough ")+.searchTest(in: source2)
let fancyPattern
= %"quick "..((%"brown" | %"black" | %"fox" | %"chicken") .. %" ")+
.. (%__)
fancyPattern.searchTest(in: source)
//===--- Parsing pairs ----------------------------------------------------===//
// The beginnings of what it will take to wrap and indent m.data in the end of
// the last test, to make it readable.
struct PairedStructure<I: Comparable> {
let bounds: Range<I>
let subStructure: [PairedStructure<I>]
}
struct Paired<T: Hashable, I: Comparable> : Pattern {
typealias Element = T
typealias Index = I
typealias MatchData = PairedStructure<I>
let pairs: Dictionary<T,T>
func matched<C: Collection>(atStartOf c: C) -> MatchResult<Index, MatchData>
where C.Index == Index, C.Element == Element
// The following requirements go away with upcoming generics features
, C.SubSequence : Collection
{
guard let closer = c.first.flatMap({ pairs[$0] }) else {
return .notFound(resumeAt: nil)
}
var subStructure: [PairedStructure<I>] = []
var i = c.index(after: c.startIndex)
var resumption: Index? = nil
while i != c.endIndex {
if let m = self.found(in: c[i..<c.endIndex]) {
i = m.extent.upperBound
subStructure.append(m.data)
resumption = resumption ?? i
}
else {
let nextI = c.index(after: i)
if c[i] == closer {
return .found(
end: nextI,
data: PairedStructure(
bounds: c.startIndex..<nextI, subStructure: subStructure))
}
i = nextI
}
}
return .notFound(resumeAt: resumption)
}
}
// Local Variables:
// swift-syntax-check-fn: swift-syntax-check-single-file
// End: