How to make sure that trees are duplicated, not shared?

[Eugene Burmako]

Hi all,

I wanted to slack off and not post this, but that's the second
accident during the last two days (and one of those accidents
disrupted the demo last week!). The question is: how do we help people
detect unintended by-reference sharing of trees when generating code
in macros?

This mistake is very easy to make, e.g. take a look at https://gist.github.com/4234441.
In that code, the author iterates over methods of a class/trait and
creates an anonymous wrapper over an instance passed to the macro,
which logs calls to those methods and redirects the calls to the
underlying instance.

Here's how the wrapper methods are generated:

def wrap_impl...(a: c.Expr[A])...
...
val methods = wrapped.declarations.collect { case m:
MethodSymbol ... => ... Select(a.tree, m.name) ... }

As a result, all generated `methods` will share a reference to the
tree that represents the argument to the macro. In this macro this
most likely won't be a problem. However if one of the methods
underwent special treatment, e.g. if it assigned manually crafted
types to the generated code, then through `a.tree` those assignments
would propagate to all the methods because ***trees are mutable***,
potentially leading to very cryptic errors.

The correct course of action here, from what I understand (Paul please
correct me if I'm overlooking something), is to use `duplicate`, as in
`a.tree.duplicate`, which creates structure-wise and attribute-wise
clone of the source tree.

So here's the question. How do we detect such situations and ideally
crash immediately? Before wrapping up, I'd like to mention that it's
not as obvious as keeping track of hashes for trees being typechecked,
because some tree might be typechecked in a throw-away context and
then inserted into some other context.

P.S. Back then when hacking Slick, Chris and I had a problem with
resetAllAttrs which unexpectedly stripped a tree shared by reference
of its attrs. Now it's no longer a danger, because resetAllAttrs has
been changed to not operate in-place, but this makes errors even more
subtle and unexpected.

Cheers,
Eugene

[Paul Phillips]

On Fri, Dec 7, 2012 at 11:49 PM, Eugene Burmako <eugene....@epfl.ch> wrote:

So here's the question. How do we detect such situations and ideally
crash immediately?

Ideally, we'd make it unnecessary to detect such situations. (Immutable Trees.) Since I don't expect that one anytime soon, plan B might be to perform extra checks on trees coming back from macros. We can see all the shared nodes in a tree easily enough; the question is whether it will be difficult to tell innocuous uses from doomed ones. I wouldn't really know that until I'd tried it.

[Eugene Burmako]

Since we allow macros to inspect their enclosing trees, they might also share nodes with the outer world. That'd be much trickier to detect.

[Paul Butcher]

I definitely second this.

It wouldn't surprise me at all if I'd made the same mistake somewhere in the innards of ScalaMock. It's not even clear to me how to examine my code to determine where I'm referencing and where I'm copying, let alone whether any such referencing is likely to be benign.

--
paul.butcher->msgCount++

Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?

http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: pa...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher

[Paul Phillips]

Monitoring tree sharing:

  https://raw.github.com/gist/4247829/0df7a4e1d7d26835d49674a70a8120ff6c22047f/gistfile1.txt

We're reverse parents. "No sharing out there! You Trees have to learn to not share, or so help me I will buy you something you want! Think about yourselves some more!"

[Eugene Burmako]

Do you have source code for the checker? I skimmed through your public activity feed at github, but didn't find anything.

[Paul Phillips]

No, I need to pull three branches together. You can bug me tomorrow if I don't push something today.

[Eugene Burmako]

Ping

[Paul Phillips]

On Wed, Dec 12, 2012 at 5:47 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

Ping

Ha, too late! I said you could bug me tomorrow, not the day after tomorrow!

... will try to get at it; being in the sf office with actual people around means my days are a lot different than I'm used to.

[Eugene Burmako]

I tried to do a crazy thing - to unconditionally duplicate everything
that's returned by a macro expansion. Surprisingly enough all the
tests pass.

On Dec 12, 5:06 pm, Paul Phillips <pa...@improving.org> wrote:

[Paul Phillips]

On Sun, Dec 16, 2012 at 6:53 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

I tried to do a crazy thing - to unconditionally duplicate everything
that's returned by a macro expansion. Surprisingly enough all the
tests pass.

How many DefTrees are created in macro tests? Maybe it is a consequence of the current limitations of macros that the tests are not entering the areas where blanket tree duplication could bite you.

[Eugene Burmako]

I doubt that macro tests cover such advanced scenarios. Though in any case it looks like auto-duplication isn't going to make things worse, but can fix some problems without the programmer even noticing.

[Paul Phillips]

On Sun, Dec 16, 2012 at 12:36 PM, Eugene Burmako <eugene....@epfl.ch> wrote:

I doubt that macro tests cover such advanced scenarios. Though in any case it looks like auto-duplication isn't going to make things worse, but can fix some problems without the programmer even noticing.

If that's a true statement, then great; but there are few things in scala in the scala implementation which adhere to absolutes and this doesn't appear a great bet to be in that group. We would do better to discuss concrete examples of where and how tree duplication will burn you; can anyone (adriaan?) offer some?

[Jason Zaugg]

Until recently, duplicate forgot the up the wasEmpty property of TypeTrees.
-jason

[Paul Phillips]

On Sun, Dec 16, 2012 at 3:07 PM, Jason Zaugg <jza...@gmail.com> wrote:

Until recently, duplicate forgot the up the wasEmpty property of TypeTrees.

I was thinking in more of a "assuming any uncontroversial fixes have been applied" way. Which trees, if automatically duplicated, will lead to errors which would not have occurred otherwise, and which trees must be duplicated to avoid errors; and most importantly, can the members of both those sets be identified deterministically, so that macro authors never even have to consider it?

[Adriaan Moors]

Trees containing definitions. They'd need to have the symbols defined by them to be duplicated and rebound as well.

[Paul Phillips]

On Mon, Dec 17, 2012 at 10:49 AM, Adriaan Moors <adriaa...@typesafe.com> wrote:

Trees containing definitions. They'd need to have the symbols defined by them to be duplicated and rebound as well.

I understand this in broad strokes... so what happens if duplicate automatically does that on DefTrees?

  newTree setSymbol oldTree.symbol.cloneSymbolAtOwner(currentOwner) // enclosingSomething, whatever

Looking around, shouldn't macros be subject to and/or have access to the code in TypingTransformer? Aren't "typing transforms" the point? Did macros reinvent this?

  abstract class TypingTransformer(unit: CompilationUnit) extends Transformer {

    var localTyper: analyzer.Typer =

      if (phase.erasedTypes)

        erasure.newTyper(erasure.rootContext(unit, EmptyTree, true)).asInstanceOf[analyzer.Typer]

      else

        analyzer.newTyper(analyzer.rootContext(unit, EmptyTree, true))

    protected var curTree: Tree = _

    override final def atOwner[A](owner: Symbol)(trans: => A): A = atOwner(curTree, owner)(trans)

    def atOwner[A](tree: Tree, owner: Symbol)(trans: => A): A = {

      val savedLocalTyper = localTyper

      localTyper = localTyper.atOwner(tree, if (owner.isModule) owner.moduleClass else owner)

      val result = super.atOwner(owner)(trans)

      localTyper = savedLocalTyper

      result

    }

    override def transform(tree: Tree): Tree = {

      curTree = tree

      tree match {

        case Template(_, _, _) =>

          // enter template into context chain

          atOwner(currentOwner) { super.transform(tree) }

        case PackageDef(_, _) =>

          atOwner(tree.symbol) { super.transform(tree) }

        case _ =>

          super.transform(tree)

      }

    }

  }

[Adriaan Moors]

The problem is we don't always know the scope of the symbols. Where should the substitution (or the re-typecheck) be performed?

[Paul Phillips]

On Mon, Dec 17, 2012 at 11:12 AM, Adriaan Moors <adriaa...@typesafe.com> wrote:

The problem is we don't always know the scope of the symbols. Where should the substitution (or the re-typecheck) be performed?

"duplicate" should be taken off tree and exposed as an extension method, the invocation of which requires an implicit parameter carrying the necessary context to correctly duplicate a tree.

[Adriaan Moors]

but how do you even automatically know that the symbol isn't used in some outer/other tree?

[Paul Phillips]

On Mon, Dec 17, 2012 at 3:06 PM, Adriaan Moors <adriaa...@typesafe.com> wrote:

but how do you even automatically know that the symbol isn't used in some outer/other tree?

That is what we have to establish. I think it's safe to say that without introducing some invariants (ideally code-enforced ones; but at least "if you always do X, then you can count on Y" style ones) we will forever be stuck with humans applying poorly informed heuristics.

For instance, it sounds to me like there's supposed to be a one-to-one relationship between DefTrees and their symbols. That has a lot higher chance of being true if we do something to preserve the truth of it. There is a whole range of actions we can take when a symbol-carrying DefTree is copied or duplicated, to add transparency even if nothing else: marking things dirty, setting up assertions to say something useful later, making symbols or trees copy-on-write/read/clone, retrospectively comparing the lives of the children of duplication, better logging.

I can't say up front what would constitute sufficient/effective constraints. What I can say is that if each macro author has to figure it out independently, we're in trouble.

[Eugene Burmako]

Wow this is something enlightening! Is that localTyper a completely valid typer with a completely valid context, just as if curTree were typechecked by Typers?

[Paul Phillips]

On Fri, Dec 21, 2012 at 8:13 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

Wow this is something enlightening! Is that localTyper a completely valid typer with a completely valid context, just as if curTree were typechecked by Typers?

Your supposition is as good as mine. I can say that this would be a good subject to pursue until we know a little more. The usage of localTyper has always been shrouded in mystery.

By inspection, it creates a new typer at each new owner seen during a transformation, so to the extent that "currentOwner" accurately reflects the current owner, localTyper should reflect the current context.