Stack overflow demangling symbol

[rocallahan]

[roc@localhost cpp_demangle]$ target/debug/examples/cppfilt
_ZN7mozilla6detail12ListenerImplINS_14AbstractThreadEZNS_20MediaEventSourceImplILNS_14ListenerPolicyE0EJNS_13TimedMetadataEEE15ConnectInternalIS2_NS_12MediaDecoderEMS8_FvOS5_EEENS_8EnableIfIXsr8TakeArgsIT1_EE5valueENS_18MediaEventListenerEE4TypeEPT_PT0_SD_EUlS9_E_JS5_EE17ApplyWithArgsImplISL_EENSC_IXsr8TakeArgsISH_EE5valueEvE4TypeERKSH_S9_

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

[rocallahan]

Unfortunately the panic handler can't catch this.

[rocallahan]

This is from a Mozilla-built libxul.so, clang 6.0.1.

c++filt 2.29.51 doesn't crash, but doesn't demangle it.

[rocallahan]

There's an infinite recursion of course:

#535 0x0000555555574f59 in <cpp_demangle::ast::TemplateArg as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c5d320, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:4733
#536 0x0000555555577de5 in <cpp_demangle::ast::TemplateParam as cpp_demangle::ast::Demangle<'subs, W>>::demangle (
    self=0x7ffff6c95120, ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:4427
#537 0x00005555555812af in <cpp_demangle::ast::Type as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c95118, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:3314
#538 0x00005555555896bb in <cpp_demangle::subs::Substitutable as cpp_demangle::ast::Demangle<'subs, W>>::demangle (
    self=0x7ffff6c95110, ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/subs.rs:41
#539 0x00005555555715fe in <cpp_demangle::ast::TypeHandle as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c951f0, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:1007
#540 0x00005555555818e3 in <cpp_demangle::ast::Type as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c951e8, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:3330
#541 0x00005555555896bb in <cpp_demangle::subs::Substitutable as cpp_demangle::ast::Demangle<'subs, W>>::demangle (
    self=0x7ffff6c951e0, ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/subs.rs:41
#542 0x00005555555715fe in <cpp_demangle::ast::TypeHandle as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c5d328, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:1007
#543 0x0000555555574f59 in <cpp_demangle::ast::TemplateArg as cpp_demangle::ast::Demangle<'subs, W>>::demangle (self=0x7ffff6c5d320, 
    ctx=0x7fffffffaa98, scope=...) at /home/roc/cpp_demangle/src/ast.rs:4733

[rocallahan]

Whether or not this symbol is valid per spec, cpp_demangle needs some kind of protection against substitution loops from invalid symbols, so I guess I'll try adding that.

[rocallahan]

Maybe the way this is supposed to work is that we can't parse a mangled name into a substitution loop... I see that Substitution::parse fails if the substitution index is invalid.

[rocallahan]

Here's what that gets parsed into:
dump.txt

[fitzgen]

IIRC, we used to disallow substitution reference cycles, but @khuey found a symbol that required a limited form of that to correctly demangle(!!)

We have the recursion limit which can be set conservatively, and this should catch this sort of bug, but it (a) might itself be incomplete, and (b) is not "automatic" in that it requires some thinking/adjusting/tweaking/checking on the users part.

Would be happy to see this story improve!

[rocallahan]

Relevant part:

    21: Type(
        TemplateParam(
            TemplateParam(
                0
            )
        )
    ),
    22: Type(
        PointerTo(
            BackReference(
                21
            )
        )
    ),

TempleParam(0) is resolved to Type(BackReference(22)), hence the loop.

[rocallahan]

The main AST is

AST = Encoding(
    Function(
        Nested(
            Template(
                CvQualifiers {
                    restrict: false,
                    volatile: false,
                    const_: false
                },
                None,
                NonSubstitution(
                    NonSubstitution(
                        7
                    )
                )
            )
        ),
        BareFunctionType(
            [
                BackReference(
                    31
                ),
                BackReference(
                    33
                ),
                BackReference(
                    10
                )
            ]
        )
    )
)

Non-substitution 7 is

    7: Prefix(
        Template(
            BackReference(
                27
            ),
            TemplateArgs(
                [
                    Type(
                        BackReference(
                            22
                        )
                    )
                ]
            )
        )
    ),

so guess that's our loop; template parameter 0 is being resolved to that BackReference.

[rocallahan]

I'm not sure yet but I suspect the problem is that the template parameter 0 in substitution 21 is looked up in the context of the use of substitution 21, not where substitution 21 first occurred.

Is this a fundamental design issue in cpp_demangle or am I misunderstanding the code?

[rocallahan]

Here's a trivial example that causes cpp_demangle to overflow the stack: when the template parameter just refers to itself: _Z1fIT_EvT_

[rocallahan]

I filed itanium-cxx-abi/cxx-abi#68 on the ambiguity about how template parameter references in substitutions are resolved.

[rocallahan]

Leaving aside that issue for now, I think the main problem here is that there's nothing preventing loops in template argument references.

[rocallahan]

One possible approach would be to have a table on the side, in DemangleContext I guess, to detect when we form a cycle through a TemplateParam.

Another possible approach would be to bring template parameters into scope one at a time during demangling, only after we've demangled it. Though this comment makes me wonder if that would actually be correct:

                // Cast operators can refer to template arguments before they
                // actually appear in the AST, so we go traverse down the tree
                // and fetch them if they exist.

Another possible approach would be to validate template parameter references as we parse, and return a parse error if there is a reference to a parameter we haven't completely parsed. But again that might not actually be correct. Also that would only work if the spec ambiguity issue was resolved to say that template parameter references in substitutions reference the template instance where they are defined.

[rocallahan]

Maybe it would be enough to track in the DemangleContext the index of the template parameter, if any, we are currently demangling. If we see a template parameter reference >= the current index, we fail or print a placeholder. I think that will prevent template-parameter-only loops.

[fitzgen]

Cast operators are the edge case, yes. They might break the index checking you describe. If so, I think we can maintain a bit set for template parameters, and whenever we enter demangling of a template parameter, we check if its bit is set. If the bit is set, that is a recursion error, otherwise we set the bit, demangle the parameter, and then unset the bit on exit.

[rocallahan]

My patch causes failures in tests I don't understand. For example:

_Z1hI1AIiEdEDTcldtfp_1gIT0_EEET_S2_

I don't understand the gIT0_E part. It seems to me that this is making g's first template parameter equal to its second template parameter, which does not exist? It looks like the existing code just passes any unknown indexes up to the enclosing context, but is there a reason why that would be a reasonable thing to do, other than just de-facto bug-compatibility?

[rocallahan]

No, it seems that template parameter references in g's template parameter list always look outside that scope...

[rocallahan]

I solved the problem by tracking which TemplateArgs we're currently processing an argument in.