[1.0.0] Recursive LocalisedString causes hard crash

[Creidhne]

What happened

Attempting to print a recursive LocalisedString via command line causes a hard crash (stack overflow).

Steps to reproduce

• Start a new game
• Type the following command:

  Code: Select all

  /c local str = {""}    str[2] = str    game.print(str)
  

Logfile attached.

Expected behaviour

A recursive LocalisedString doesn't make any sense. Expected behaviour is just a nice error message instead of the hard crash.

[valneq]

If a recursive localized string does not make sense, why do you try to create one?

[DaveMcW]

Expected behaviour is just a nice error message instead of the hard crash.

A table that allows self-references is Turing complete . Therefore you are asking Wube to solve the halting problem.

[eradicator]

Expected behaviour is just a nice error message instead of the hard crash.

A table that allows self-references is Turing complete . Therefore you are asking Wube to solve the halting problem.

Detecting recursive tables in lua isn't quite as difficult. You just need to keep references to all ancestors of a table. Any table that is it's own ancestor is recursive.

[Creidhne]

If a recursive localized string does not make sense, why do you try to create one?

Because I wondered what the game would do in this situation.

Since your question has a strong implicit smell of "Then this bug report is useless. Nothing to fix, just stop doing that", I'll add a little something. This bug enables a user to crash all clients + the server on a multiplayer game (by accident or out of malicious intent). Even if you disable commands on the server, it could still be triggered by other means like .cfg files. cfg files would maybe only crash the player doing it, even with request_translation... I didn't check, and fixing the stack overflow itself requires probably much less dev time than checking all the LocalisedString usage.

A long digression about the Turing-completeness and halting problem applied to LocalisedString

A table that allows self-references is Turing complete.

This makes as much sense as saying that "philosophy is blue". Philosophy is an abstract concept that doesn't emit/reflect/diffuse light, so it doesn't have a color. Tables by themselves aren't a formalism to describe programs (or a machine able to execute a program), so tables can't be said to be Turing-complete (or not).

So let's formulate the problem precisely. When doing game.print(someTable), the game reads someTable and a bunch of .cfg file to generate a string, which is then printed. So it can be said that "someTable" defines a program that takes a text input (the .cfg files), and generates a text output. Normally we'd have to also precise the validity domain of the "someTable" thing, and exactly how the conversion is done depending on the data in "someTable". But let's forget and just suppose that recursive tables are fine. So here's a good formulation of the problem: is the "LocalisedString" formalism for program description (which happen to be represented Lua table) Turing complete ?

If we take the article you linked, it presents multiple theorems to show that a language (= formalism) is Turing complete. For none of them, recursion is a sufficient condition.

As a simple proof that the "LocalisedString" language is not Turing complete: it is not possible (to my knowledge) to write a "program" (= localised string) to remove/replace the last character/symbol of an input (= value in the .cfg file). Since such a program is possible on a Turing machine, The LocalisedString language is not Turing-complete.

Therefore you are asking Wube to solve the halting problem.

Even if the LocalisedString language was Turing-complete, the bug I presented is easily solvable. The halting problem states that there is no magic program M that takes any other program P and input I, and answer the question "does P(I) terminates ? Accepted answers: yes & no".

This does not prevent the existence of program that answers "does P(I) terminates ? Accepted answers: no & I don't know". For this bug, you just need to detect that you're about to call "translate(someTable)" again while you're still evaluating "translate(someTable)". There's no rocket science in that: Lua detects circular "require" easily for example.

[Rseding91]

Thanks for the report however as with last time this was reported we decided it wasn't worth making the logic slower to guard against a case where there's literally never a reason to do that. 80194

In the same realm as:

Code: Select all

local p = game.player.print; p("thing")

- just don't do that.