Reflection-based printing traverses cycles and runs out of stack

[burg]

Whenever %? is used on a data structure with cycles (such as servo's util::tree), it will traverse cycles and run out of stack. This could be fixed with some expensive but easy thing like keeping a list of already-traversed boxed things, and declining to traverse twice.

[graydon]

non-critical for 0.6, de-milestoning

[pnkfelix]

On issue #6180 @Aatch wanted this problem nominated for Maturity Milestone 3: "Feature Complete"

(I don't know if it belongs there or with milestone 5: "Production ready" or even further beyond, the "far off" milestone. I get the impression that %? is supposed to generate text that corresponds roughly to Rust expressions, and we do not have a literal syntax for potentially-cyclic graph structure.)

[Aatch]

@pnkfelix my motivation for "Feature Complete" is mostly that, as a feature, it is technically broken. While we don't have a literal syntax for cyclic structures, the current behaviour of "recurse until we either run out of stack or are killed by the OS" isn't acceptable. Not in my eyes anyway. "Production Ready" would be ok, but I wouldn't agree with anything further.

[pnkfelix]

@Aatch Out of curiosity: would you be satisfied in the short term if passing a cyclic structure to "%?" caused a fail!(relatively quickly) ?

I don't know if that's the sort of thing where we could do that now and plug in a different behavior later, under a (potentially wrong-headed) philosophy that clients should not be actively trying to rely on/observe fail!, or if somehow we would be committing to a fail! now and forever in the future on cyclic structure. I just thought I'd mention it as an option that would at least require less design effort in the short term.

[Aatch]

@pnkfelix well @huonw suggested a recursion limit on IRC. Since it is obviously impossible to adhere to the "Rust expression" thing with a cyclic data structure anyway. I haven't look at the code, but that seems like it would be fairly easy to do.

Either way, we need to detect or deal cycles, and rather than fail!ing I would prefer to see something like {...} in the output. It's less ambiguous and doesn't stop the program there and then. We should be encouraging developers to use things like debug!, so the runtime equivalent of a tantrum seems counter-productive to that.

However, anything is better than stack/memory exhaustion.

[huonw]

FWIW, Python does the ... thing:

>>> L = [1,2,3]
>>> L.append(L)
>>> L
[1, 2, 3, [...]]

[pnkfelix]

@Aatch A recursion limit with something like {...} seems reasonable to me. I assume we'll reserve the freedom to put in a different rendering engine on %? in the future, since it seems intended for humans to use for debugging (and not e.g. for output that another tool is expecting to parse).

[Aatch]

I don't see why not. If this:

let a = @mut A { a: None }; let mut v = Some(a); a.a <-> v;
  io::println(fmt!("%?",a));

printed this: {a:Some({...})}, or some nested version, then I would probably understand that it's because it's cyclic.

[thestinger]

Python cycle checks on operations like == too. Handling @ properly is non-trivial in a lot of places.

[pnkfelix]

@thestinger cycle-checking on a generic == may or may not be related to this bug, depending on what approach [^1] we want to take for it.

Anyway, I agree with your statement that handling @ properly is non-trivial.

[^1] E.g. we could go the route of Scheme and implement a total predicate, a la SRFI 85 ; my understanding is that this approach not that bad in terms of common-case overhead as long as one delays actually using the full Hopcroft+Karp algorithm until after you've already attempted the traditional algorithm to bounded depth. There's another approach to the same problem presented by Adams and Dybvig from ICFP 2008, but I don't remember the details of that work.

[pnkfelix]

(to be honest I haven't thought terribly hard about whether its feasible to actually implement the total predicate generically in a statically typed language, or at least in this statically typed language; so take my previous comment with a large grain of salt)

[graydon]

accepted for production-ready milestone

[emberian]

Reproduces with:

struct A {
    a: Option<@mut A>
}

fn main() {
    let a = @mut A { a: None };
    let mut v = Some(a);
    std::util::swap(&mut a.a, &mut v);
    printfln!(a);
}

[pnkfelix]

Assigning P-low.

[pnkfelix]

(note that we make no commitments for 1.0 as to what format {:?} uses for its output, and thus there's no backcompat risk here.)