Re: [scala-internals] Data Dependency Graph

[Naftoli Gugenheim]

What do you mean specifically by data dependency?

On Mon, Jul 6, 2015 at 2:18 PM peetswee <mben...@gmail.com> wrote:

Hi,

Is there a good way to extract the data dependency graph from Scala code?

Thanks

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[peetswee]

Sorry, I meant a program dependence graph.

[peetswee]

Sorry, I meant to delete the thread and make a new one with a new title...  I mean to ask:

Is there a good way to extract a program dependency graph from Scala code?  Should I look into plugins and Icode?

[Naftoli Gugenheim]

Can you be more specific?

On Mon, Jul 6, 2015, 4:03 PM peetswee <mben...@gmail.com> wrote:

Sorry, I meant to delete the thread and make a new one with a new title...  I mean to ask:

Is there a good way to extract a program dependency graph from Scala code?  Should I look into plugins and Icode?

--

[Haoyi Li]

https://github.com/lihaoyi/acyclic does exactly that. It currently just checks some invariants and discards it, but it should be quite easy to dump the file-level dependency graph to a file, or granularize it so that it's more fine grained (e.g. class level)

On Mon, Jul 6, 2015 at 1:03 PM, peetswee <mben...@gmail.com> wrote:

Sorry, I meant to delete the thread and make a new one with a new title...  I mean to ask:

Is there a good way to extract a program dependency graph from Scala code?  Should I look into plugins and Icode?

--

[Naftoli Gugenheim]

I can't access it.

On Mon, Jul 6, 2015, 5:26 PM peetswee <mben...@gmail.com> wrote:

I mean like the one in this paper http://delivery.acm.org/10.1145/30000/24041/p319-ferrante.pdf?ip=137.82.252.83&id=24041&acc=ACTIVE%20SERVICE&key=FD0067F557510FFB.26E2C50968A06846.4D4702B0C3E38B35.4D4702B0C3E38B35&CFID=526049262&CFTOKEN=92655648&__acm__=1436212749_5dfc0a8f8a454d8580de7950d0004e77

[peetswee]

I mean like the one described in this paper: https://www.cs.utexas.edu/~pingali/CS395T/2009fa/papers/ferrante87.pdf

Here is a snippet of the abstract describing a PDG (program dependency graph).

On Monday, July 6, 2015 at 1:15:57 PM UTC-7, nafg wrote:

[peetswee]

I actually took found it earlier while searching through older posts here.  I was meaning program dependency more like for example:
(1)   B=5
(2)   C=1
(3)   D=B+10

Then (3) requires (1) to execute before it, but (2) can just execute whenever because it doesn't depend on anything.

I'll take a look at your plugin again, I might just be confused and not understand it.  Thanks

[Matan Safriel]

I think in general, you will have to walk the AST, tracing which symbols rely on other symbols. This very typically means writing (or forking) a compiler plugin.

I am not sure how complicated would it be to capture all dependencies in all cases, but a good place to start would be observing some compilation units' AST. You can use https://github.com/lihaoyi/acyclic as inspiration for traversing scala Abstract Syntax Trees - for example look at ExtractDependenciesByInheritanceTraverser there. You can add a println there to print the entire AST.

I hope you realize this means learning to fiddle compiler api, and observing an intermediary representation created by the compiler - which is not the scala you're used to seeing. 

One thing to note is that dependencies may be dynamic (determined at runtime) and impossible to deduce through static analysis; consider logic branching or the simple case of an assignment with a match statement - and it no longer makes sense to speak in naive terms of "A depends on B". But for naive dependency extraction, I would try walking the AST, in which case the mentioned plugin is a good yet demanding example, if you're willing to learn the compiler api as you go.