Add trait for function callgraph extraction, to allow "builtin attribute"-style UDA semantic checks

[dlangBugzillaToGithub]

Andrej Mitrovic (@AndrejMitrovic) reported this on 2013-09-06T08:07:47Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=10979

CC List

• Boris Carvajal
• Nick Sabalausky
• Adam D. Ruppe
• mhh

Description

Currently, attributes such as @safe work on the entire possible callgraph of a function, meaning:

-----
void _safe(bool state) @safe
{
    if (state)
        foo();
    else
        bar(); // error, can't call system function 'bar'
}

void foo() @safe
{
}

void bar()
{
}
-----

However for user-defined types we currently cannot implement such semantic checks, even if we used compile-time checking using traits and static asserts.

The user should be able to extract the entire possible callgraph tree of a function, and then use this to implement his own semantic checks via a template.

Here's an example use-case and some pseudo-code on how this might look:

-----
enum NoMalloc;  // UDA type

// this may or may not allocate and therefore breaks the @NoMalloc guarantee.
void func(bool state) @NoMalloc
{
    if (state)
        does_allocate();
    else
        does_not_allocate();
}

void does_not_allocate() @NoMalloc { }
void does_allocate() { }

/**
    Ensure that $(D func) defines the semantics of @NoMalloc:
    making sure it itself is marked with @NoMalloc, and that
    all the functions in the callgraph are @NoMalloc as well,
    and that none of the functions in the callgraph are the
    druntime function $(D malloc).
*/
template CheckNoMalloc(alias func)
{
    // pseudocode
    static assert(hasUDA!(func, NoMalloc));

    // pseudocode
    foreach (callfunc; getCallgraph!func)
    {
        // a more appropriate check could be made
        static assert(!is(callfunc == core.stdc.malloc) ||
                      hasUDA!(callfunc, NoMalloc));
    }
}

void main()
{
    // user-defined check (usually part of a constraint)
    CheckNoMalloc!func;
    func();
}
-----

The 'CheckNoMalloc' template can then be used in e.g. template constraints, to verify that a function can only call other @NoMalloc functions, and that none of these functions ever call the druntime function malloc (yes it's only an extern(C) declaration, but any check could be made here).

This is just one example use-case, there could potentially be many more.

Of course, the downside of the malloc check is can't be 100% reliable, since user-code could internally define an extern(C) function, or could use pointers to get to a function that uses a function such as 'malloc'.

So that particular check may not be too reliable, but the benefit is the ability to add semantic checking to UDAs based on the possible callgraph, so you could implement pure/trusted-style UDAs that work recursively.

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2013-09-06T08:14:30Z

Anyway this will likely need a lot more thought and discussion before an implementation is even considered. E.g. the first problem I can think of, is what happens when a function in the graph is private? Can we still call __traits on it? It probably warrants a NG discussion.

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2013-09-06T08:15:07Z

Also, credit to the idea goes to Adam D. Ruppe.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-09-11T13:43:24Z

Extending the type system like this possibly my main use case for UDAs. A successive step is to make the tests more automatic, calling templates/functions like CheckNoMalloc for all the functions tagged @NoMalloc in the compilation unit.

[dlangBugzillaToGithub]

bus_dbugzilla commented on 2013-10-08T14:07:06Z

(In reply to comment #1)
> Anyway this will likely need a lot more thought and discussion before an
> implementation is even considered. E.g. the first problem I can think of, is
> what happens when a function in the graph is private? Can we still call
> __traits on it? It probably warrants a NG discussion.

Reflection normally bypasses visibility restrictions such as private. Maybe I just haven't paid enough attention, but I've never seen a case in any language where privates were hidden from reflection.

[dlangBugzillaToGithub]

destructionator commented on 2013-10-08T16:10:32Z

I just wrote this on the newsgroup and want it to be here too:

Though, my proposed __traits could perhaps be improved to just 
offer two things:

__traits(getFunctionsCalled, function)

returns a tuple of all functions called. These would ideally be 
in the form of symbols.

__traits(functionBodyAvailable, function)

true if the source was available to the compiler.


And that's it: the rest is done in the library using existing 
language features. Then we can decide in library code if a 
missing attribute is a problem based on if the body was available 
or not.

Note that this isn't specific to the gc: it would provide the 
necessary foundation for all kinds of library extensions in the 
same vein as @safe, with the possibility of automatic inference 
from the prototype + presence of body.


 * * *


To get the entire call graph, your helper library function would do getFunctionsCalled recursively. It would be a pain to actually build a big return tuple since you can't ~= a symbol.... but you could easily enough pass a visitor template to the helper function which is instantiated with each thingy.

But anyway, recursive templates are a solved problem, so however we decide to do it, we can keep the compiler simple.

[dlangBugzillaToGithub]

maxhaton commented on 2021-01-24T07:22:00Z

keep an eye out for typefunctions (to anyone reading this for some reason)

[dlangBugzillaToGithub]

destructionator commented on 2021-01-24T14:16:14Z

Type functions aren't a substitute for this at all. Even if you had them, they'd still need a way to introspect the function's calls which is what this enhancement is requesting.

[dlangBugzillaToGithub]

boris2.9 commented on 2021-01-25T16:01:47Z

Reopening. There is no reason to close it.