5

Consider the following Swift expression

println(Generic<Foo, Bar>(1))

Normally, one would read this as a generic call to the constructor Generic<Foo, Bar> with the arguments (1).

println( Generic<Foo,Bar>(1) )

However, when re-arranging the tokens a bit, it could also represent two separate comparisons, for example if Generic and Foo were some poorly named numeric variables:

println(Generic < Foo, Bar > (1))
// or, with proper parenthesis
println((Generic < Foo), (Bar > 1))

What we can observe here is that an expression with a generic constructor like this is highly ambiguous, and not easy to disambiguate even for humans. The problem here is that Swift doesn't have a new keyword for constructors, which makes them ambiguous with method calls and operators in some cases. Thus, I am interested in how the Swift compiler (parser) manages to disambiguate the above expressions. Is the way it is parsed dependant on the context (types, variables, functions) or can it be resolved by the parser?

Clashsoft
  • 11,553
  • 5
  • 40
  • 79
  • I don't understand what you're asking. Maybe post some example code to demonstrate what you mean? – oisdk Jul 27 '15 at 12:24
  • 1
    I did??? I want to know how the compiler knows that this is a generic constructor for `Generic` rather than two separate comparison operators. – Clashsoft Jul 27 '15 at 12:26
  • I was looking for just a line that runs in a playground, if you know what I mean. (rather than the placeholder words - it's difficult to mentally parse if I don't know what you mean) – oisdk Jul 27 '15 at 12:30
  • 1
    That's exactly the problem - in a context-free grammar, the compiler cannot check for variables or types outside the expression either. – Clashsoft Jul 27 '15 at 12:32
  • You say there are two possible interpretations of the above expression. An example of each interpretation - with the variables signed values and all that - that can just give me a simple `println` would really help. I *think* I know what you're getting at, but it's difficult to understand. Is `Generic` a function in the first interpretation, and then a variable in the second? – oisdk Jul 27 '15 at 12:37
  • It doesn't matter: The Swift parser shouldn't know either when parsing it. – Clashsoft Jul 27 '15 at 12:40
  • 1
    Whitespace matters to the parser. – Jean-Philippe Pellet Jul 27 '15 at 12:40
  • I understand what you're asking now (I think) [and here's the kind of thing I was looking for](http://i.imgur.com/YRrSZfA.png). Just a way for people to understand the two different interpretations you're talking about, and how it really is ambiguous. I understand what you're saying - that the compiler shouldn't need any of that extra information - but *humans* might, to understand what you're asking. – oisdk Jul 27 '15 at 12:47
  • Possible duplicate of [How does Swift disambiguate Type Arguments in Expression Contexts?](https://stackoverflow.com/questions/36387657/how-does-swift-disambiguate-type-arguments-in-expression-contexts) – Clashsoft Sep 10 '17 at 20:40

2 Answers2

1

The answer is simple: The compiler simply does't allow you to declare these variables:

struct Generic<T, U> {

    init(_ i: Int) {}
}
struct Foo {}
struct Bar {}

print(Generic<Foo, Bar>(1))

// error
let Foo = 0      // invalid redeclaration of Foo
let Bar = 3      // invalid redeclaration of Bar
let Generic = 5  // invalid redeclaration of Generic
print(Generic<Foo, Bar>(1))

Making either the variables or the type declarations in another source file the current declaration "overrides" the other one.

Qbyte
  • 12,753
  • 4
  • 41
  • 57
  • This makes sense if `Generic`, `Foo` and `Bar` are defined within the same source file. But what happens if they are declared somewhere else? Also, these errors seem like they are raised at semantic analysis rather than parsing. – Clashsoft Jul 27 '15 at 15:12
  • @Clashsoft The curent declaration "overrides" the other one. (updated my answer) – Qbyte Jul 27 '15 at 15:41
  • But what if both are declared somewhere else? Also, this still doesn't explain how the *parser* (not the semantic analyzer) handles the input. – Clashsoft Jul 27 '15 at 16:14
  • @Clashsoft at least in a Playground where you put the declarations in different source files you get the same error as in the first example (invalid redeclaration) since they are both in the same scope. – Qbyte Jul 27 '15 at 16:41
0

There are at least three ways to deal with this (and probably more).

  1. Combine parsing with a symbol table. As the parser encounters a generic type, it is added to a symbol table. When a parser subsequently encounters a generic type symbol it switches to parsing generic parameters rather than comparison operators.

  2. The second (used by JS++ and described here) is to use a GLR parser and parse both branches. Then in the type analysis phase, the generic parse branch is selected.

  3. Arbitrary lookahead matching Constructor = Symbol "<" GenericParameters ">" "(" CallParameters ")" . (ie. >(...) is always a generic constructor call).

Interestingly, this code:

struct A<T, U> {
    init(_ i: Int) {}
}

struct B {}
struct C {}

print(A<B, C>(1))

Succeeds, while this code:

struct A<T, U> {
    init(_ i: Int) {}
}

struct B {}
struct C {}

print(A<B, C>1)

Gives this error:

error: binary operator '<' cannot be applied to operands of type 'A<_, _>.Type' and 'B.Type'
print(A<B, C>1)
      ~^~

This is interesting because it indicates that Swift uses the third option: arbitrary lookahead. Their grammar is probably something like this (vastly simplified):

Constructor = Symbol "<" GenericParameters ">" "(" CallParameters ")" .
Less = Terminal "<" Terminal .

Expr = Constructor | Less .
Alec Thomas
  • 19,639
  • 4
  • 30
  • 24