http://d.puremagic.com/issues/show_bug.cgi?id=10979

           Summary: Add trait for function callgraph extraction, to allow
                    "builtin attribute"-style UDA semantic checks
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: andrej.mitrovich@gmail.com


--- Comment #0 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-09-06 08:07:47 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10979



--- Comment #1 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-09-06 08:14:30 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10979



--- Comment #2 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-09-06 08:15:07 PDT ---
Also, credit to the idea goes to Adam D. Ruppe.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10979


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #3 from bearophile_hugs@eml.cc 2013-09-11 13:43:24 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10979


Nick Sabalausky <cbkbbejeap@mailinator.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |cbkbbejeap@mailinator.com


--- Comment #4 from Nick Sabalausky <cbkbbejeap@mailinator.com> 2013-10-08 14:07:06 PDT ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10979



--- Comment #5 from Adam D. Ruppe <destructionator@gmail.com> 2013-10-08 16:10:32 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------