Hey @davedufresne !

We managed to build a working parser for something like ledger-cli. The 5000-line sample file that we tried to parse (naively) took a massive amount of time to parse (the first iteration even took 13 minutes). We got it down to a few minutes.

The popFirst() on strings is really expensive, as it reallocates a new copy of the string. We managed to speed it up a little bit by using a CharacterView, but still, this mutates the underlying _StringCore type.

As Stream only needs the ArrayLiteralConvertible and the popFirst(), we implemented a new struct that doesn't copy at all. It only changes the "pointer" to the first element in the array. We also tried storing String.CharacterView in this struct, but that was a lot slower.

struct ImmutableCharacters: Stream {
    var characters: [Character]
    var start: Int = 0

    init(string: String) {
        characters = Array(string.characters)
    }

    init(arrayLiteral elements: Character...) {
        characters = elements
    }

    mutating func popFirst() -> Character? {
        guard start < characters.count else { return nil }
        let oldStart = start
        start += 1
        return characters[oldStart]
    }
}

This helped a lot for speed. Our file now parses in 2 seconds. This is still quite slow (we'd like to be able to parse it in milliseconds).

When running this in Instruments, we noticed at least half a second was spent retaining/releasing things. Almost certainly, the characters array. If could work on something like an UnsafeBufferPointer, there would be no need for retain or release. However, this is hard to make work with both the Parsec.string parser, and also the ArrayLiteralConvertible that Stream inherits from.

Have you thought about these issues, and do you have any more ideas for how to make this fast? We're happy to help out. Maybe we could integrate the ImmutableCharacters struct already? It's a drop-in replacement.

Hello again!

I present the Linux-compatible package! I've documented the source, but let me know if there is anything that seems off.

Closes #7

Here are some "fun" things I learned on the way (hopefully putting it here will also make it more Google-able for others):

Unicode order is not consistent between platforms

"\u{2000}"..."\u{200D}" // creates a Range on macOS, crashes on Ubuntu
"\u{200D}"..."\u{2000}" // creates a Range on Ubuntu, crashes on macOS

Protocol / implementation variable names can cause linker crashes

https://bugs.swift.org/browse/SR-2598

This is actually the problem that previously forced me to use -whole-module-optimization. To fix it, I moved the DefaultTokenParser stuff into the same file as the protocol definition. Unfortunately, this puts the TokenParser file at > 1000 lines.

Greetings,

I am having trouble building this library on Ubuntu 16.04 (Swift 3.0.2). The issue may be related to a compiler bug, but I decided to post it here in case you thought otherwise. The code I'll refer to below is that in https://github.com/hkgumbs/SwiftParsec/master, which has only compatibility changes. I think the quickest way to play with Ubuntu 16.04 would be use Docker: docker run -it -v $PWD:/code -w /code swiftdocker/swift bash.

Sources

swift build
...
	Cross-reference to module 'SwiftParsec'
	... TokenParser
	... in an extension in module 'SwiftParsec'
	... identifier
	... with type GenericParser<String, τ_0_0.UserState, String>

I found a SO post that described similar symptoms, and the recommendation there is to use the -whole-module-optimization flag.

swift build -Xswiftc -whole-module-optimization -c release

The release configuration is what ultimately tells the swift-build-tool to look elsewhere for dependency mappings (Source). Otherwise, swift build fails with unable to open dependencies file '/code/.build/debug/SwiftParsec.build/CharacterMembership.d'.

Tests

These flags don't port as nicely to tests. I think this is the major issue since I want to verify that the changes and optimizations are not affecting the behavior of the library. The root of the problem seems to be that I cannot force -c release in test builds. One workaround is run swift test -Xswiftc -whole-module-optimization then manually modify .build/debug.yaml:

--- a/.build/debug.yaml
+++ b/.build/debug.yaml
@@ -22 +22 @@ commands:
-    enable-whole-module-optimization: false
+    enable-whole-module-optimization: true
@@ -38 +38 @@ commands:
-    enable-whole-module-optimization: false
+    enable-whole-module-optimization: true

Once you make those changes, you can run the swift-build-tool manually, and it will compile the tests. However, you'll still see a problem at link time. The output is mostly gibberish - this is the farthest I've gotten:

/usr/bin/swift-build-tool -f /code/.build/debug.yaml test
...

Like I mentioned at the start, this doesn't seem to be an issue with your project specifically, but I thought I'd bring it up just in case you had any ideas.

Cheers!

I changed the initializations to overcome Swift 4.2 compiler error. I also had to change a string in a test case that failed -- no idea how it ran successfully before.

Adds a variant of oneOf() with a ClosedInterval<Character> argument, allowing code similar to the following:

let alnum = 
        StringParser.oneOf("A"..."Z")
    <|> StringParser.oneOf("a"..."z") 
    <|> StringParser.oneOf("0"..."9")

Hi,

I am using Swift Package Manager and I added this package with its latest version 4.0.0. I am using Xcode 12.5 and I got a compiler error. Unfortunately, the existing fix https://github.com/davedufresne/SwiftParsec/commit/e8d092de0c206decadfbd15c4b5a82209594bed0 (fix compiler error in Xcode 12.5) is not part of release 4.0.0 and I have to refer to the master branch. Would be great if a release 4.0.1 would be tagged including this important fix.

Kind regards, Marco

Hey @davedufresne ! Awesome project. We're thinking of using it for a project. The code looks really solid.

I want to get the source position out, so that we can parse into an AST that is annotated with the source positions. Using the public API, this is currently not possible, right? Would you mind adding this if I create a PR?

Hi, Thanks for a great library!

I am porting a parser from FParsec to SwiftParsec and it's gone pretty well. One difference in behaviour is operator matching. I would like to parse '>=' and if that fails '>', but the operator behaviour doesn't allow this e.g when constructing the OperatorTable:

[
        binary(">=", function: { Expr.Comparison($0, .Ge, $1) }, assoc: .none),
        binary("<=", function: { Expr.Comparison($0, .Le, $1) }, assoc: .none),
        binary("<", function: { Expr.Comparison($0, .Lt, $1) }, assoc: .none),
        binary(">", function: { Expr.Comparison($0, .Gt, $1) }, assoc: .none)
],

So for var1 > 3 FParsec will attempt '>=' and then succeed on '>'. Is there a way to replicate this behaviour?

Thanks again.

Hi Dave..

I have been trying to use the Expression parser to build an AST for a project.... So I dove into the code of the library and pulled out your example in the ExpressionParser.swift file..

Here's my code:

import SwiftParsec
let java = LanguageDefinition<()>.javaStyle
let lexer = GenericTokenParser(languageDefinition: java)
let integer = lexer.integer

indirect enum T {
  case I(Int)
  case MulOp(T,T)
  case DivOp(T,T)
  case AddOp(T,T)
  case SubOp(T,T)
 }

 func binary( name: String, function: (T, T) -> T, assoc: Associativity ) -> Operator<String, (), T> {
     let opParser = StringParser.string(name) *> GenericParser(result: function)
     return .infix(opParser, assoc)
 }

 let opTable: OperatorTable<String, (), T> = [
     [
        binary(name:"*", function: {a,b in return T.MulOp(a,b)}, assoc: .left),
        binary(name:"/", function: {a,b in return T.DivOp(a,b)}, assoc: .left)
     ],
     [
        binary(name:"+", function: {a,b in return T.AddOp(a,b)}, assoc: .left),
        binary(name:"-", function: {a,b in return T.SubOp(a,b)}, assoc: .left)
     ]
 ]

 let openingParen = StringParser.character("(")
 let closingParen = StringParser.character(")")
 let decimal = GenericTokenParser<()>.decimal
 let tint = {a in T.I(a)} <^> integer
 let expression = opTable.makeExpressionParser { expression in
     expression.between(openingParen, closingParen) <|>
         tint <?> "simple expression"

 } <?> "expression"

expression.runSafe(userState: (), sourceName:"", input: "345+143*54")

The problem is that i get an error "Playground execution failed: error: Untitled Page.xcplaygroundpage:56:24: error: cannot convert value of type 'GenericParser<String, (), (T, T) -> T>' to expected argument type 'GenericParser<_, , (, _) -> _>' return .infix(opParser, assoc) " The error is referring to the type of opParser.

Everything appears ok to me... but then I'm not a swift (or functional programming) expert.

Any ideas?

Thanks bob

I've been studying the testRecursive method in CombinatorParsersTests.swift because I'm trying to understand how the whole recursive thing works. In order to test my understanding, I was playing around with different input and have discovered a test failure.

If I change the matching and expected definitions to this:

        let matching = ["3-(1+2)", "3-1+2", "3-(1-(3+1))"]
        let expected = [3-(1+2), 3-1+2, 3-(1-(3+1))]

It fails with the message, CombinatorParsersTests.swift:1114: error: -[SwiftParsecTests.CombinatorTests testRecursive] : XCTAssertEqual failed: ("4") is not equal to ("0")

Whether or not this is an actual failure depends on the intended associativity of the operators, since that isn't stated anywhere, and the context leads me to believe Swift-like associativity is desired, I thought I would note it here; sorry if that is not what is intended.

I am also sorry I can't offer a fix, but to offer a fix would require my understanding recursive and that is the very reason I'm here looking at recursive! 🤷‍♂️

/Users/.../qubv/SourcePackages/checkouts/SwiftParsec/Sources/SwiftParsec/TokenParser.swift:435:24: Cannot convert value of type 'GenericParser<String, Self.UserState, Character?>' to expected argument type 'GenericParser<String, Self.UserState, Character>'

/Users/.../qubv/SourcePackages/checkouts/SwiftParsec/Sources/SwiftParsec/TokenParser.swift:451:28: Unable to infer complex closure return type; add explicit type to disambiguate

Hi! I love this library. I want to use this to parse byte sequence [UInt8]. How can I extend? I tried to extends like:

extension Parsec
where StreamType.Iterator.Element == UInt8, Result ==  Token {
    internal static func satisfy(
        _ predicate: @escaping (UInt8) -> Bool
        ) -> GenericParser<StreamType, UserState, Result> {
        
        return tokenPrimitive(
            tokenDescription: { String(reflecting: $0) },
            nextPosition: { position, elem in
                
                var pos = position
                pos.updatePosition(elem)
                
                return pos
                
        },
            match: { elem in
                
                predicate(elem) ? Token.seq([elem]) : nil
        })
    }
    
    static func oneOf(_ list: [UInt8]) -> GenericParser<StreamType, UserState, Result> {
    }
}

But I got an error with pos.updatePosition ..