Factorio Forums

Posted: **Sat Oct 17, 2020 9:55 pm**

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.

Posted: **Sat Oct 17, 2020 10:23 pm**

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

Posted: **Sat Oct 17, 2020 10:45 pm**

Creidhne wrote: Sat Oct 17, 2020 9:55 pmExpected 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.

Posted: **Sat Oct 17, 2020 10:57 pm**

DaveMcW wrote: Sat Oct 17, 2020 10:45 pm
Creidhne wrote: Sat Oct 17, 2020 9:55 pmExpected 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.

Posted: **Sun Oct 18, 2020 10:22 am**

valneq wrote: Sat Oct 17, 2020 10:23 pm 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

DaveMcW wrote: Sat Oct 17, 2020 10:45 pm 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.

DaveMcW wrote: Sat Oct 17, 2020 10:45 pm 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.

Posted: **Mon Oct 19, 2020 3:50 pm**

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.

Factorio Forums

[1.0.0] Recursive LocalisedString causes hard crash

[1.0.0] Recursive LocalisedString causes hard crash

Re: [1.0.0] Recursive LocalisedString causes hard crash

Re: [1.0.0] Recursive LocalisedString causes hard crash

Re: [1.0.0] Recursive LocalisedString causes hard crash

Re: [1.0.0] Recursive LocalisedString causes hard crash

Re: [1.0.0] Recursive LocalisedString causes hard crash