Parser combinators are not thread-safe

[scabug]

JSON.parseFull or parseRaw randomly fails with NPE. In order to get the stacktrace, one must use -Xint flag. It works fine most of the time and randomly fails. When I run a simple script that parses JSON.parseFull("{"hello": "dude"}"), when run in a loop 10K times, it fails a few times during the run (again, randomly). Below is the stacktrace...

java.lang.NullPointerException: null
at scala.util.parsing.combinator.Parsers$NoSuccess.(Parsers.scala:132) ~[scala-library.jar:na]
at scala.util.parsing.combinator.Parsers$Failure.(Parsers.scala:159) ~[scala-library.jar:na]
at scala.util.parsing.combinator.Parsers$$anonfun$acceptIf$1.apply(Parsers.scala:499) ~[scala-library.jar:na]
...

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4929?orig=1
Reporter: Ilya Sterin (isterin)
Affected Versions: 2.9.2
Attachments:

• scala_nullpointer.txt (created on Jul 20, 2012 7:15:08 PM UTC, 21953 bytes)

[scabug]

Brian Maso (bmaso) said (edited on Oct 7, 2011 4:15:51 PM UTC):
I just ran in to this same NPE, at the same line in Parsers.NoSuccess. No that the NPE occurred when processing tens of thousands of JSON docs (Twitter API tweets, actually). The NPE seems to have occurred on a line of JSON input document that is well formed. The JSON parser is the Dispatch JSON parser, version 0.8.5.

The tack trace I received is the same as the original reporter'sfor the last few stack frames:

java.lang.NullPointerException: null
at scala.util.parsing.combinator.Parsers$NoSuccess.(Parsers.scala:132) ~[scala-library.jar:na]
at scala.util.parsing.combinator.Parsers$Failure.(Parsers.scala:159) ~[scala-library.jar:na]
at scala.util.parsing.combinator.Parsers$$anonfun$acceptIf$1.apply(Parsers.scala:499) ~[scala-library.jar:na]
at scala.util.parsing.combinator.Parsers$$anonfun$acceptIf$1.apply(Parsers.scala:497) ~[scala-library.jar:na]

The offending line is 132. AFAICT, The only way an NPE would happen at this point is if the "next", "lastNoSuccess", or "lastNoSuccess.next" members are null. "lastNoSuccess" is a var in the outer class, so while the not-null check at line 132 would seem to guarantee "lastNoSuccess" is not null, the highly infrequent and random occurrence of the NPE points to a race condition -- perhaps the "lastNoSuccess" member is somehow being changed to null after the null check, but before the "< lastNoPosition.next" check?

[scabug]

@retronym said:
The stdlib Parser combinators aren't threadsafe, and hence neither is JSON.parseRaw

You should construct a new scala.util.parsing.json.Parser for each request, and use a pool of them if performance counts.

This should be better documented in both the parser and JSON packages.

http://scala-programming-language.1934581.n4.nabble.com/Scala-Parsers-are-not-thread-safe-td2243477.html
http://www.scala-lang.org/node/8356

[scabug]

@acruise said:
Can we either change the title of this bug, or file a new one, about the lack of thread safety?

[scabug]

@dcsobral said:
I'm troubled by the fix to this bug. It makes phrase and NoSuccess slower, by introducing a lazy val, and DynamicVariable and an Option. Now, phrase shouldn't be much of a problem, but normal parsing process will create tons of NoSuccess, even if the parser succeeds (one for every option that was considered and failed).

Now, I'm all for correctness -- it's easy to make something fast if it doesn't have to work. However, I can't think of any reason why parser should be shared between multiple threads. Why not simply instantiate it on demand? JSON itself could be turned into a class, and the object turned into a factory.

Here's the pull request.

[scabug]

@paulp said:
Well, I sat on this for months because I wasn't real excited about it, and finally I asked adriaan to make a determination and he said go with it, although it wasn't the most ringing endorsement either. But mostly, neither of us can afford to engage with peripheral library issues right now. If you want to send another pull request that'd be great.

[scabug]

@dcsobral said:
Sure. Close the ticket and I'll look into possible performance issues. Happily, I have the benchmark setup I wrote for Range.foreach.

[scabug]

Stephen Judkins (stephenjudkins) said:
Thanks for looking into possible performance implications. A few points:

• I did some benchmarking (of various JSON strings) and did not, to my recollection, see a major drop in performance. The cost of creating NoSuccess instances was small relative to everything else the parser does.
• In our case (IRC protocol parser) constructing the parser instances was more expensive than the parsing itself. This is obviously a function of the very small size of messages, and relatively complexity of parser, but just creating a new non-threadsafe parser for every parse job would not be an acceptable solution for many people.
• I know this solution is fugly. I played around with other solutions that don't use mutable state, but the only reasonable one I came up with (state monad containing lastNoSuccess) would involve breaking the existing parser API. If anyone has any superior suggestions I'd love to help implement them.

[scabug]

@dcsobral said:
Have you tried without {{lazy}}? I don't see it gaining much.

[scabug]

Stephen Judkins (stephenjudkins) said:
I recall (it's been awhile) that lazy val is used instead of val to avoid initialization order problems, not as an optimization.

We should have actual benchmark data before we continue this discussion. Have you written one yet? If not, would you like me to do so?

[scabug]

@dcsobral said:
I have a framework for the benchmark. http://github.com/dcsobral/scala-foreach-benchmark. What is nice about it is that you can put different versions of the compiler in a directory, and it will run the tests through caliper for each compiler version.

I haven't written the benchmark for this yet -- I won't have time for that before Friday, and I didn't have any particular regex parser in mind.

However, I just recalled Scalate is based on Scala parsers, and I think they do have some benchmarks. If so, it would be a nice, non-trivial, real-world test case.

[scabug]

jsh (jhooda) said:
Wondering when it will be resolved? Another issue is deep recursion inherent in the code, which affects performance (see stack trace):

The exception was noticed in
org.scala-lang
scala-library
2.9.1

[scabug]

@dcsobral said:
@jsh A solution has been provided. The only thing's missing is benchmark to see if there's no serious performance impact.

[scabug]

@SethTisue said (edited on Jan 4, 2013 3:01:32 AM UTC):
the "cure" here was worse than the disease, at least for me. scala/scala@dce6b34 broke my app under 2.10. the commit introduces a ThreadLocal, without providing any way of calling remove() on it to clean up. so my no-longer-used Thread isn't eligible for garbage collection anymore like it was on 2.9.

I was able to work around it as follows by running this code when I'm done parsing:

val field = getClass.getDeclaredField("scala$util$parsing$combinator$Parsers$$lastNoSuccessVar")
field.setAccessible(true)
val field2 = classOf[scala.util.DynamicVariable[_]].getDeclaredField("tl")
field2.setAccessible(true)
field2.get(field.get(this)).asInstanceOf[java.lang.ThreadLocal[_]].remove()
field.set(this, null)

but, yuck.

the good news is the lastNoSuccess thing is deprecated in 2.10, so it can be removed in 2.11.

[scabug]

Stephen Judkins (stephenjudkins) said:
Agreed: yuck. Given this report, I'm inclined to agree with skeptics that this shouldn't have been merged in.

I'm confused, though. From http://docs.oracle.com/javase/6/docs/api/java/lang/ThreadLocal.html:
`
Each thread holds an implicit reference to its copy of a thread-local variable as long as the thread is alive and the ThreadLocal instance is accessible; after a thread goes away, all of its copies of thread-local instances are subject to garbage collection (unless other references to these copies exist).

This implies that a non-alive thread can be garbage-collected even if aremove` hasn't been called. If ThreadLocal follows this contract, this implies that the NoSuccess instance contains a reference.

Further, I can't reproduce this: watching this contrived example [https://gist.github.com/8df7bba520c7f3a56ac3] run on 2.10 in VisualVM indicates no leakage. I suppose there might be a circular reference back to the Thread somewhere in your particular parser?

As a form of penance I'd be happy to help you track down this particular issue.