I recently looked at issue 3821 (detecting recursive data structures in std.format to avoid a crash) [1]. I think, it could be easily fixed by collecting pointers to objects where toString is called and preventing a second call. Unfortunately (some instances of) format would not be pure anymore and this entails a lot of other functions which would loose it's purity. (And it doesn't work in CTFE, but that's an other story.)

The weird thing is, that the original call to the function (formatObject in std.format) would behave like a pure function: The result is always the same and the non local changes are temporary and not visible from the outside. The problem is, that this function should indeed return something different, when it calls itself (indirectly) with identical parameters once more to prevent the original call from never returning...

I have not yet a deep understanding of purity, so maybe there is a way arround this problem I cannot see due to my limited knowledge. Any ideas?

And, maybe somewhat heretical: Does the advantage of purity here really outweight the problems it causes?

[1] https://issues.dlang.org/show_bug.cgi?id=3821

On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:
> I have not yet a deep understanding of purity, so maybe there is a way arround this problem I cannot see due to my limited knowledge. Any ideas?

Here's a generic pattern you could use:

T foo(Value x) pure
{
  static T impl(Value x, ref State s) pure
  {
    // ...code recursively calling impl and tracking state with mutable s
  }
  State s;
  return impl(x, s);
}

On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:

> The problem is, that this function should indeed return something different, when it calls itself (indirectly) with identical parameters once more to prevent the original call from never returning...

This should indeed be NOT the same parameters. There should be a hidden additional parameter (lets name it "called_internal"), that be false in the original call and true in a recursion. With this it's perfectly pure while returning something different if called by itself.

On Sunday, 29 December 2019 at 10:40:23 UTC, sarn wrote:
> On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:
>> I have not yet a deep understanding of purity, so maybe there is a way arround this problem I cannot see due to my limited knowledge. Any ideas?
>
> Here's a generic pattern you could use:
>
> T foo(Value x) pure
> {
>   static T impl(Value x, ref State s) pure
>   {
>     // ...code recursively calling impl and tracking state with mutable s
>   }
>   State s;
>   return impl(x, s);
> }

Yes, exactly this.

On Sunday, 29 December 2019 at 10:46:07 UTC, Dominikus Dittes Scherkl wrote:
> This should indeed be NOT the same parameters. There should be a hidden additional parameter (lets name it "called_internal"), that be false in the original call and true in a recursion. With this it's perfectly pure while returning something different if called by itself.

Thanks for your ideas, but unfortunately I think these cannot be used here. The reason is, that I have no control over the intermediate steps, so I cannot pass that additional parameter (ref State s in sarn's code). These intermediate steps consist of calls to toString, which then do, whatever the user want's them to do, and eventually call format again and format calls formatObject with identical parameters. I can't change the signature of toString, nor make the users implement that...

On Sunday, 29 December 2019 at 10:46:07 UTC, Dominikus Dittes Scherkl wrote:
> On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:
>
>> The problem is, that this function should indeed return something different, when it calls itself (indirectly) with identical parameters once more to prevent the original call from never returning...
>
> This should indeed be NOT the same parameters. There should be a hidden additional parameter (lets name it "called_internal"), that be false in the original call and true in a recursion. With this it's perfectly pure while returning something different if called by itself.

The problem with this approach is that the recursion may not be direct. For example:

import std;

struct A
{
    B[] bs;
    void toString(W)(ref W w) { formattedWrite(w, "%s", bs[0]); }
}

struct B
{
    C[] cs;
    void toString(W)(ref W w) { formattedWrite(w, "%s", cs[0]); }
}

struct C
{
    A[] as;
    void toString(W)(ref W w) { formattedWrite(w, "%s", as[0]); }
}

void main()
{
    A[] as = [A()];
    B[] bs = [B()];
    C[] cs = [C(as)];
    as[0].bs = bs;
    bs[0].cs = cs;

    writeln(as[0]); // crashes
}

Solving this is probably halting-equivalent in the general case (that is, impossible), so I'm not inclined to worry too much about it. If someone writes an infinite loop in their toString method, that's their problem.