www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 10979] New: Add trait for function callgraph extraction, to allow "builtin attribute"-style UDA semantic checks

reply d-bugmail puremagic.com writes:
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



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: -------
Sep 06 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10979




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: -------
Sep 06 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10979




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: -------
Sep 06 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10979


bearophile_hugs eml.cc changed:

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



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: -------
Sep 11 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10979


Nick Sabalausky <cbkbbejeap mailinator.com> changed:

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



14:07:06 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.


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: -------
Oct 08 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10979




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: -------
Oct 08 2013