Allow to perfom several different tracing in the same pass.

Change-Id: I8d96808e1570035437ac2db3524b722e826fb728

22 files changed, 1302 insertions, 187 deletions

diff --git a/jack/src/com/android/jack/Jack.java b/jack/src/com/android/jack/Jack.java
index 9e012b6c..e26adc82 100644
--- a/jack/src/com/android/jack/Jack.java
+++ b/jack/src/com/android/jack/Jack.java
@@ -25,6 +25,7 @@ import com.android.jack.analysis.defsuses.DefUsesAndUseDefsChainRemover;
 import com.android.jack.analysis.defsuses.UseDefsChecker;
 import com.android.jack.analysis.dfa.reachingdefs.ReachingDefinitions;
 import com.android.jack.analysis.dfa.reachingdefs.ReachingDefinitionsRemover;
+import com.android.jack.analysis.tracer.ExtendingOrImplementingClassFinder;
 import com.android.jack.backend.ResourceWriter;
 import com.android.jack.backend.dex.ClassAnnotationBuilder;
 import com.android.jack.backend.dex.ClassDefItemBuilder;
@@ -145,12 +146,11 @@ import com.android.jack.shrob.seed.SeedPrinter;
 import com.android.jack.shrob.seed.remover.FieldSeedMarkerRemover;
 import com.android.jack.shrob.seed.remover.MethodSeedMarkerRemover;
 import com.android.jack.shrob.seed.remover.TypeSeedMarkerRemover;
-import com.android.jack.shrob.shrink.ExtendingOrImplementingClassFinder;
 import com.android.jack.shrob.shrink.FieldShrinker;
 import com.android.jack.shrob.shrink.Keeper;
 import com.android.jack.shrob.shrink.MethodShrinker;
 import com.android.jack.shrob.shrink.Shrinking;
-import com.android.jack.shrob.shrink.StructurePrinter;
+import com.android.jack.shrob.shrink.ShrinkStructurePrinter;
 import com.android.jack.shrob.shrink.StructurePrinting;
 import com.android.jack.shrob.shrink.TypeShrinker;
 import com.android.jack.shrob.shrink.remover.FieldKeepMarkerRemover;
@@ -466,7 +466,7 @@ public abstract class Jack {
             request.addFeature(AdaptResourceFileContent.class);
           }
         }
-        if (config.get(StructurePrinter.STRUCTURE_PRINTING).booleanValue()) {
+        if (config.get(ShrinkStructurePrinter.STRUCTURE_PRINTING).booleanValue()) {
           request.addProduction(StructurePrinting.class);
         }
 
@@ -777,7 +777,7 @@ public abstract class Jack {
       planBuilder.append(MappingPrinter.class);
     }
     if (productions.contains(StructurePrinting.class)) {
-      planBuilder.append(StructurePrinter.class);
+      planBuilder.append(ShrinkStructurePrinter.class);
     }
     if (features.contains(Shrinking.class) || features.contains(Obfuscation.class)) {
       appendShrobMarkerRemoverPlan(planBuilder);
@@ -989,7 +989,7 @@ public abstract class Jack {
       planBuilder.append(MappingPrinter.class);
     }
     if (productions.contains(StructurePrinting.class)) {
-      planBuilder.append(StructurePrinter.class);
+      planBuilder.append(ShrinkStructurePrinter.class);
     }
     {
       SubPlanBuilder<JDefinedClassOrInterface> typePlan =
@@ -1224,7 +1224,7 @@ public abstract class Jack {
       planBuilder.append(MappingPrinter.class);
     }
     if (productions.contains(StructurePrinting.class)) {
-      planBuilder.append(StructurePrinter.class);
+      planBuilder.append(ShrinkStructurePrinter.class);
     }
     if (features.contains(Shrinking.class) || features.contains(Obfuscation.class)) {
       appendShrobMarkerRemoverPlan(planBuilder);
@@ -1478,7 +1478,7 @@ public abstract class Jack {
       planBuilder.append(MappingPrinter.class);
     }
     if (productions.contains(StructurePrinting.class)) {
-      planBuilder.append(StructurePrinter.class);
+      planBuilder.append(ShrinkStructurePrinter.class);
     }
 
     {
diff --git a/jack/src/com/android/jack/Options.java b/jack/src/com/android/jack/Options.java
index 2662b856..e4313857 100644
--- a/jack/src/com/android/jack/Options.java
+++ b/jack/src/com/android/jack/Options.java
@@ -28,7 +28,7 @@ import com.android.jack.shrob.obfuscation.SourceFileRenamer;
 import com.android.jack.shrob.obfuscation.annotation.AnnotationRemover;
 import com.android.jack.shrob.obfuscation.annotation.ParameterAnnotationRemover;
 import com.android.jack.shrob.seed.SeedPrinter;
-import com.android.jack.shrob.shrink.StructurePrinter;
+import com.android.jack.shrob.shrink.ShrinkStructurePrinter;
 import com.android.jack.shrob.spec.Flags;
 import com.android.jack.transformations.renamepackage.PackageRenamer;
 import com.android.jack.util.filter.AllMethods;
@@ -557,9 +557,9 @@ public class Options {
         CodeItemBuilder.EMIT_SYNTHETIC_LOCAL_DEBUG_INFO, emitSyntheticDebugInfo);
 
     if (typeAndMemberListing != null) {
-      configBuilder.set(StructurePrinter.STRUCTURE_PRINTING, true);
+      configBuilder.set(ShrinkStructurePrinter.STRUCTURE_PRINTING, true);
       configBuilder.setString(
-          StructurePrinter.STRUCTURE_PRINTING_FILE, typeAndMemberListing.getAbsolutePath());
+          ShrinkStructurePrinter.STRUCTURE_PRINTING_FILE, typeAndMemberListing.getAbsolutePath());
     }
 
     if (jayceOutZip != null) {
diff --git a/jack/src/com/android/jack/analysis/tracer/AbstractTracerBrush.java b/jack/src/com/android/jack/analysis/tracer/AbstractTracerBrush.java
new file mode 100644
index 00000000..d9670d21
--- /dev/null
+++ b/jack/src/com/android/jack/analysis/tracer/AbstractTracerBrush.java
@@ -0,0 +1,172 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.analysis.tracer;
+
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+import com.android.sched.marker.Marker;
+
+import javax.annotation.Nonnull;
+
+/**
+ * Default base class for {@link TracerBrush} implementations.
+ */
+public abstract class AbstractTracerBrush<M extends BaseTracerMarker> implements TracerBrush {
+
+  private final boolean traceEnclosingMethod;
+
+  @Nonnull
+  private final Class<M> markerClass;
+
+  @Nonnull
+  private final Class<? extends Marker> seedMarkerClass;
+
+  public AbstractTracerBrush(boolean traceEnclosingMethod,
+      @Nonnull Class<M> markerClass,
+      @Nonnull Class<? extends Marker> seedMarkerClass) {
+    this.traceEnclosingMethod = traceEnclosingMethod;
+    this.markerClass = markerClass;
+    this.seedMarkerClass = seedMarkerClass;
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JDefinedClassOrInterface type) {
+    return markIfNecessary(type);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JDefinedClassOrInterface type) {
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JMethod type) {
+    return markIfNecessary(type);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JMethod type) {
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JField type) {
+    return markIfNecessary(type);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JField type) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+    return isSeed(type);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JMethod method) {
+    return isSeed(method);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JMethod method) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JField field) {
+    return isSeed(field);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JField field) {
+  }
+
+  @Override
+  public boolean startTraceOverridingMethod(@Nonnull JMethod method) {
+    return traceMarked(method) && mustTraceOverridingMethod(method);
+  }
+
+  @Override
+  public void endTraceOverridingMethod(@Nonnull JMethod method) {
+  }
+
+  @Override
+  public boolean traceMarked(@Nonnull JNode node) {
+    return isMarked(node);
+  }
+
+  @Override
+  public void endTraceMarked(@Nonnull JNode node) {
+  }
+
+
+  protected boolean markIfNecessary(@Nonnull JNode node) {
+    synchronized (node) {
+      if (!node.containsMarker(markerClass)) {
+        node.addMarker(createMarkerFor(node));
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Nonnull
+  protected abstract M createMarkerFor(@Nonnull JNode node);
+
+  protected boolean isMarked(@Nonnull JNode node) {
+    synchronized (node) {
+      return node.containsMarker(markerClass);
+    }
+  }
+
+  protected boolean isSeed(@Nonnull JNode node) {
+    return node.containsMarker(seedMarkerClass);
+  }
+
+  protected boolean mustTraceOverridingMethod(@Nonnull JMethod method) {
+    synchronized (method) {
+      BaseTracerMarker marker = method.getMarker(markerClass);
+      if (marker != null) {
+        return marker.mustTraceOverridingMethods();
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public void setMustTraceOverridingMethods(@Nonnull JMethod method) {
+    synchronized (method) {
+      BaseTracerMarker marker = method.getMarker(markerClass);
+      assert marker != null;
+      marker.setMustTraceOverridingMethods(true);
+    }
+  }
+
+  @Override
+  public boolean startTraceEnclosingMethod() {
+    return traceEnclosingMethod;
+  }
+
+  @Override
+  public void endTraceEnclosingMethod() {
+  }
+
+}
diff --git a/jack/src/com/android/jack/analysis/tracer/BaseTracerMarker.java b/jack/src/com/android/jack/analysis/tracer/BaseTracerMarker.java
new file mode 100644
index 00000000..bca1f406
--- /dev/null
+++ b/jack/src/com/android/jack/analysis/tracer/BaseTracerMarker.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.analysis.tracer;
+
+import com.android.sched.marker.Marker;
+
+import javax.annotation.Nonnull;
+
+/**
+ * Base {@link Marker} that must be extended along with {@link AbstractTracerBrush}.
+ */
+public abstract class BaseTracerMarker implements Marker {
+
+  private boolean mustTraceOverridingMethods = false;
+
+  public void setMustTraceOverridingMethods(boolean mustTraceOverridingMethods) {
+    this.mustTraceOverridingMethods = mustTraceOverridingMethods;
+  }
+
+  public boolean mustTraceOverridingMethods() {
+    return mustTraceOverridingMethods;
+  }
+
+  @Nonnull
+  @Override
+  public Marker cloneIfNeeded() {
+    return this;
+  }
+
+}
diff --git a/jack/src/com/android/jack/analysis/tracer/ComposedTracerBrush.java b/jack/src/com/android/jack/analysis/tracer/ComposedTracerBrush.java
new file mode 100644
index 00000000..2af611ea
--- /dev/null
+++ b/jack/src/com/android/jack/analysis/tracer/ComposedTracerBrush.java
@@ -0,0 +1,269 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.analysis.tracer;
+
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+import com.android.sched.util.findbugs.SuppressFBWarnings;
+
+import java.util.BitSet;
+import java.util.Stack;
+
+import javax.annotation.Nonnull;
+
+/**
+ * {@link TracerBrush} for running several tracing in the same pass.
+ */
+public class ComposedTracerBrush implements TracerBrush {
+
+  @Nonnull
+  private final TracerBrush[] brushes;
+
+  @Nonnull
+  private final Stack<BitSet> composedStatus = new Stack<BitSet>();
+
+  /*
+   * Because this is just configuration we don't care to store internally an externally visible
+   * mutable array.
+   */
+  @SuppressFBWarnings("EI_EXPOSE_REP2")
+  public ComposedTracerBrush(@Nonnull TracerBrush[] brushes) {
+    this.brushes = brushes;
+    BitSet initialAllEnabled = new BitSet(brushes.length);
+    initialAllEnabled.set(0, brushes.length);
+    composedStatus.push(initialAllEnabled);
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JDefinedClassOrInterface type) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTrace(type);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTrace(@Nonnull JDefinedClassOrInterface type) {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTrace(type);
+    }
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JMethod type) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTrace(type);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTrace(@Nonnull JMethod type) {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTrace(type);
+    }
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JField type) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTrace(type);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTrace(@Nonnull JField type) {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTrace(type);
+    }
+  }
+
+  @Override
+  public boolean startTraceOverridingMethod(@Nonnull JMethod method) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTraceOverridingMethod(method);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTraceOverridingMethod(@Nonnull JMethod method) {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTraceOverridingMethod(method);
+    }
+  }
+
+  @Override
+  public void setMustTraceOverridingMethods(@Nonnull JMethod method) {
+    BitSet currentStatus = composedStatus.peek();
+    for (int i = 0; i < brushes.length; i++) {
+      if (currentStatus.get(i)) {
+        brushes[i].setMustTraceOverridingMethods(method);
+      }
+    }
+  }
+
+  @Override
+  public boolean traceMarked(@Nonnull JNode node) {
+    boolean isMarked = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].traceMarked(node);
+      nextStatus.set(i, b);
+      isMarked |= b;
+    }
+    if (isMarked) {
+      composedStatus.push(nextStatus);
+    }
+    return isMarked;
+  }
+
+  @Override
+  public boolean startTraceEnclosingMethod() {
+    boolean startTrace = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTraceEnclosingMethod();
+      nextStatus.set(i, b);
+      startTrace |= b;
+    }
+    if (startTrace) {
+      composedStatus.push(nextStatus);
+    }
+    return startTrace;
+  }
+
+  @Override
+  public void endTraceEnclosingMethod() {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTraceEnclosingMethod();
+    }
+  }
+
+  @Override
+  public void endTraceMarked(@Nonnull JNode node) {
+    composedStatus.pop();
+    for (TracerBrush config : brushes) {
+      config.endTraceMarked(node);
+    }
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTraceSeed(type);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JDefinedClassOrInterface method) {
+    composedStatus.pop();
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JMethod method) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTraceSeed(method);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JMethod method) {
+    composedStatus.pop();
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JField field) {
+    boolean status = false;
+    BitSet currentStatus = composedStatus.peek();
+    BitSet nextStatus = new BitSet(brushes.length);
+    for (int i = 0; i < brushes.length; i++) {
+      boolean b = currentStatus.get(i) && brushes[i].startTraceSeed(field);
+      nextStatus.set(i, b);
+      status |= b;
+    }
+    if (status) {
+      composedStatus.push(nextStatus);
+    }
+    return status;
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JField field) {
+    composedStatus.pop();
+  }
+}
diff --git a/jack/src/com/android/jack/shrob/shrink/ExtendingOrImplementingClassFinder.java b/jack/src/com/android/jack/analysis/tracer/ExtendingOrImplementingClassFinder.java
index 1eb0e5ca..00d44c88 100644
--- a/jack/src/com/android/jack/shrob/shrink/ExtendingOrImplementingClassFinder.java
+++ b/jack/src/com/android/jack/analysis/tracer/ExtendingOrImplementingClassFinder.java
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-package com.android.jack.shrob.shrink;
+package com.android.jack.analysis.tracer;
 
 import com.android.jack.ir.ast.JClass;
 import com.android.jack.ir.ast.JClassOrInterface;
diff --git a/jack/src/com/android/jack/shrob/shrink/ExtendingOrImplementingClassMarker.java b/jack/src/com/android/jack/analysis/tracer/ExtendingOrImplementingClassMarker.java
index 6b2091e3..823653b0 100644
--- a/jack/src/com/android/jack/shrob/shrink/ExtendingOrImplementingClassMarker.java
+++ b/jack/src/com/android/jack/analysis/tracer/ExtendingOrImplementingClassMarker.java
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-package com.android.jack.shrob.shrink;
+package com.android.jack.analysis.tracer;
 
 import com.android.jack.ir.ast.JDefinedClass;
 import com.android.jack.ir.ast.JDefinedClassOrInterface;
diff --git a/jack/src/com/android/jack/shrob/shrink/Tracer.java b/jack/src/com/android/jack/analysis/tracer/Tracer.java
index bda4f04b..5fd5464a 100644
--- a/jack/src/com/android/jack/shrob/shrink/Tracer.java
+++ b/jack/src/com/android/jack/analysis/tracer/Tracer.java
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-package com.android.jack.shrob.shrink;
+package com.android.jack.analysis.tracer;
 
 import com.android.jack.Jack;
 import com.android.jack.ir.ast.Annotable;
@@ -51,7 +51,6 @@ import com.android.jack.ir.ast.JModifier;
 import com.android.jack.ir.ast.JNameValuePair;
 import com.android.jack.ir.ast.JNewArray;
 import com.android.jack.ir.ast.JNewInstance;
-import com.android.jack.ir.ast.JNode;
 import com.android.jack.ir.ast.JParameter;
 import com.android.jack.ir.ast.JPrimitiveType.JPrimitiveTypeEnum;
 import com.android.jack.ir.ast.JType;
@@ -75,22 +74,26 @@ import javax.annotation.Nonnull;
  * A visitor that traces dependencies
  */
 @Description("traces dependencies")
-public abstract class Tracer extends JVisitor {
+public class Tracer extends JVisitor {
 
   @Nonnull
   protected static final com.android.sched.util.log.Tracer tracer = TracerFactory.getTracer();
 
-  private final boolean traceEnclosingMethod;
-
   @Nonnull
   public Logger logger = LoggerFactory.getLogger();
 
-  public abstract boolean markIfNecessary(@Nonnull JNode node);
+  @Nonnull
+  private final TracerBrush brush;
 
-  public abstract boolean isMarked(@Nonnull JNode node);
+  public Tracer(@Nonnull TracerBrush brush) {
+    this.brush = brush;
+  }
 
-  public Tracer(boolean traceEnclosingMethod) {
-    this.traceEnclosingMethod = traceEnclosingMethod;
+  public void run(@Nonnull JDefinedClassOrInterface type) throws Exception {
+    if (brush.startTraceSeed(type)) {
+      trace(type);
+      brush.endTraceSeed(type);
+    }
   }
 
   public void trace(@Nonnull JType t) {
@@ -116,7 +119,7 @@ public abstract class Tracer extends JVisitor {
     if (superClOrI instanceof JDefinedClassOrInterface) {
       JDefinedClassOrInterface definedSuperClOrI = (JDefinedClassOrInterface) superClOrI;
       for (JMethod method : definedSuperClOrI.getMethods()) {
-        if (isMarked(method) && mustTraceOverridingMethod(method)) {
+        if (brush.startTraceOverridingMethod(method)) {
           JMethodId methodId = method.getMethodId();
           JType returnType = method.getType();
           JMethod implementation =
@@ -125,6 +128,7 @@ public abstract class Tracer extends JVisitor {
             trace(methodId, implementation.getEnclosingType(), returnType,
                 true /* mustTraceOverridingMethods */);
           }
+          brush.endTraceOverridingMethod(method);
         }
       }
 
@@ -138,15 +142,11 @@ public abstract class Tracer extends JVisitor {
     }
   }
 
-  protected abstract boolean mustTraceOverridingMethod(@Nonnull JMethod method);
-
-  protected abstract void setMustTraceOverridingMethods(@Nonnull JMethod method);
-
   protected void trace(@Nonnull JDefinedClassOrInterface t) {
-    if (markIfNecessary(t)) {
+    if (brush.startTrace(t)) {
       traceAnnotations(t);
       for (JMethod m : t.getMethods()) {
-        if (!isMarked(m) && (JMethod.isClinit(m) || isNullaryConstructor(m))) {
+        if ((JMethod.isClinit(m) || isNullaryConstructor(m))) {
           trace(m);
         }
       }
@@ -166,11 +166,12 @@ public abstract class Tracer extends JVisitor {
 
         if (JModifier.isAnonymousType(t.getModifier())) {
           trace(t.getEnclosingType());
-          if (traceEnclosingMethod) {
+          if (brush.startTraceEnclosingMethod()) {
             JMethod enclosingMethod = ((JDefinedClass) t).getEnclosingMethod();
             if (enclosingMethod != null) {
               trace(enclosingMethod);
             }
+            brush.endTraceEnclosingMethod();
           }
         }
 
@@ -180,14 +181,31 @@ public abstract class Tracer extends JVisitor {
           trace(values);
         }
       }
+
+      for (JField field : t.getFields()) {
+        if (brush.startTraceSeed(field)) {
+          trace(field);
+          brush.endTraceSeed(field);
+        }
+      }
+
+      for (JMethod method : t.getMethods()) {
+        if (brush.startTraceSeed(method)) {
+          trace(method);
+          brush.endTraceSeed(method);
+        }
+      }
+
+      brush.endTrace(t);
     }
   }
 
   protected void trace(@Nonnull JField f) {
-    if (markIfNecessary(f)) {
+    if (brush.startTrace(f)) {
       trace(f.getEnclosingType());
       trace(f.getType());
       traceAnnotations(f);
+      brush.endTrace(f);
     }
   }
 
@@ -225,7 +243,7 @@ public abstract class Tracer extends JVisitor {
     if (foundMethod != null) {
       trace(foundMethod);
       if (mustTraceOverridingMethods) {
-        setMustTraceOverridingMethods(foundMethod);
+        brush.setMustTraceOverridingMethods(foundMethod);
       }
     }
 
@@ -234,12 +252,13 @@ public abstract class Tracer extends JVisitor {
           ((LocalMarkerManager) receiverType).getMarker(ExtendingOrImplementingClassMarker.class);
       if (marker != null) {
         for (JDefinedClass subClass : marker.getExtendingOrImplementingClasses()) {
-          if (isMarked(subClass)) {
+          if (brush.traceMarked(subClass)) {
             JMethod implementation = findImplementation(mid, returnType, subClass);
             if (implementation != null) {
               trace(implementation);
-              setMustTraceOverridingMethods(implementation);
+              brush.setMustTraceOverridingMethods(implementation);
             }
+            brush.endTraceMarked(subClass);
           }
         }
       }
@@ -247,7 +266,7 @@ public abstract class Tracer extends JVisitor {
   }
 
   protected void trace(@Nonnull JMethod m) {
-    if (markIfNecessary(m)) {
+    if (brush.startTrace(m)) {
       trace(m.getEnclosingType());
       traceAnnotations(m);
       for (JParameter arg : m.getParams()) {
@@ -266,6 +285,7 @@ public abstract class Tracer extends JVisitor {
           accept(body);
         }
       }
+      brush.endTrace(m);
     }
   }
 
diff --git a/jack/src/com/android/jack/analysis/tracer/TracerBrush.java b/jack/src/com/android/jack/analysis/tracer/TracerBrush.java
new file mode 100644
index 00000000..1b73f611
--- /dev/null
+++ b/jack/src/com/android/jack/analysis/tracer/TracerBrush.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.analysis.tracer;
+
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+
+import javax.annotation.Nonnull;
+
+/**
+ * A customization for piloting the {@link Tracer}.
+ */
+public interface TracerBrush {
+
+  boolean startTrace(@Nonnull JMethod method);
+  void endTrace(@Nonnull JMethod method);
+
+  boolean startTrace(@Nonnull JField field);
+  void endTrace(@Nonnull JField field);
+
+  boolean startTrace(@Nonnull JDefinedClassOrInterface type);
+  void endTrace(@Nonnull JDefinedClassOrInterface type);
+
+  boolean startTraceSeed(@Nonnull JDefinedClassOrInterface type);
+  void endTraceSeed(@Nonnull JDefinedClassOrInterface type);
+
+  boolean startTraceSeed(@Nonnull JMethod method);
+  void endTraceSeed(@Nonnull JMethod method);
+
+  boolean startTraceSeed(@Nonnull JField field);
+  void endTraceSeed(@Nonnull JField field);
+
+  boolean startTraceOverridingMethod(@Nonnull JMethod method);
+  void endTraceOverridingMethod(@Nonnull JMethod method);
+
+  boolean startTraceEnclosingMethod();
+  void endTraceEnclosingMethod();
+
+  boolean traceMarked(@Nonnull JNode node);
+  void endTraceMarked(@Nonnull JNode node);
+
+  void setMustTraceOverridingMethods(@Nonnull JMethod method);
+}
diff --git a/jack/src/com/android/jack/shrob/seed/remover/TypeSeedMarkerRemover.java b/jack/src/com/android/jack/shrob/seed/remover/TypeSeedMarkerRemover.java
index b9c42046..35889877 100644
--- a/jack/src/com/android/jack/shrob/seed/remover/TypeSeedMarkerRemover.java
+++ b/jack/src/com/android/jack/shrob/seed/remover/TypeSeedMarkerRemover.java
@@ -18,7 +18,6 @@ package com.android.jack.shrob.seed.remover;
 
 import com.android.jack.ir.ast.JDefinedClassOrInterface;
 import com.android.jack.shrob.seed.SeedMarker;
-import com.android.jack.shrob.shrink.ExtendingOrImplementingClassMarker;
 import com.android.sched.item.Description;
 import com.android.sched.schedulable.RunnableSchedulable;
 import com.android.sched.schedulable.Transform;
@@ -29,7 +28,7 @@ import javax.annotation.Nonnull;
  * A {@code Schedulable} that removes markers used for seed support on types.
  */
 @Description("Removes seed-related markers on types.")
-@Transform(remove = {SeedMarker.class, ExtendingOrImplementingClassMarker.class})
+@Transform(remove = SeedMarker.class)
 public class TypeSeedMarkerRemover implements RunnableSchedulable<JDefinedClassOrInterface> {
 
   @Override
diff --git a/jack/src/com/android/jack/shrob/shrink/KeepMarker.java b/jack/src/com/android/jack/shrob/shrink/KeepMarker.java
index 469c7d45..1a1e588e 100644
--- a/jack/src/com/android/jack/shrob/shrink/KeepMarker.java
+++ b/jack/src/com/android/jack/shrob/shrink/KeepMarker.java
@@ -16,12 +16,12 @@
 
 package com.android.jack.shrob.shrink;
 
+import com.android.jack.analysis.tracer.BaseTracerMarker;
 import com.android.jack.ir.ast.JDefinedClassOrInterface;
 import com.android.jack.ir.ast.JField;
 import com.android.jack.ir.ast.JMethod;
 import com.android.sched.item.Description;
 import com.android.sched.marker.DynamicValidOn;
-import com.android.sched.marker.Marker;
 
 import javax.annotation.Nonnull;
 
@@ -29,22 +29,7 @@ import javax.annotation.Nonnull;
  * Indicates that this class or member should not be removed when shrinking.
  */
 @Description("Indicates that this class or member should not be removed when shrinking.")
-public class KeepMarker implements Marker {
-
-  private boolean mustTraceOverridingMethods = false;
-
-  public void setMustTraceOverridingMethods(boolean mustTraceOverridingMethods) {
-    this.mustTraceOverridingMethods = mustTraceOverridingMethods;
-  }
-
-  public boolean mustTraceOverridingMethods() {
-    return mustTraceOverridingMethods;
-  }
-
-  @Override
-  public Marker cloneIfNeeded() {
-    return this;
-  }
+public class KeepMarker extends BaseTracerMarker {
 
   @DynamicValidOn
   public boolean isValidOn(@Nonnull JDefinedClassOrInterface type) {
diff --git a/jack/src/com/android/jack/shrob/shrink/Keeper.java b/jack/src/com/android/jack/shrob/shrink/Keeper.java
index f2764e92..3f88c19a 100644
--- a/jack/src/com/android/jack/shrob/shrink/Keeper.java
+++ b/jack/src/com/android/jack/shrob/shrink/Keeper.java
@@ -16,19 +16,15 @@
 
 package com.android.jack.shrob.shrink;
 
+import com.android.jack.analysis.tracer.ExtendingOrImplementingClassMarker;
+import com.android.jack.analysis.tracer.Tracer;
 import com.android.jack.ir.ast.JDefinedClassOrInterface;
-import com.android.jack.ir.ast.JField;
-import com.android.jack.ir.ast.JMethod;
-import com.android.jack.ir.ast.JNode;
 import com.android.jack.shrob.seed.SeedMarker;
 import com.android.jack.shrob.spec.KeepModifier;
 import com.android.sched.item.Description;
 import com.android.sched.schedulable.Constraint;
 import com.android.sched.schedulable.RunnableSchedulable;
-import com.android.sched.schedulable.Transform;
-import com.android.sched.util.config.HasKeyId;
-import com.android.sched.util.config.ThreadConfig;
-import com.android.sched.util.config.id.BooleanPropertyId;
+import com.android.sched.schedulable.Use;
 
 import javax.annotation.Nonnull;
 
@@ -37,103 +33,18 @@ import javax.annotation.Nonnull;
  * shrinking.
  */
 @Description("Marks all classes and members that will be kept when shrinking.")
-@Transform(add = KeepMarker.class)
-@Constraint(need = {ExtendingOrImplementingClassMarker.class, SeedMarker.class})
-@HasKeyId
+@Constraint(need = {ExtendingOrImplementingClassMarker.class})
+@Use(KeeperBrush.class)
 public class Keeper implements RunnableSchedulable<JDefinedClassOrInterface> {
 
-  private static class Visitor extends Tracer {
-
-    private Visitor() {
-      super(ThreadConfig.get(KEEP_ENCLOSING_METHOD).booleanValue());
-    }
-
-    @Override
-    public void trace(@Nonnull JDefinedClassOrInterface type) {
-      if (!isMarked(type)) {
-        super.trace(type);
-
-        for (JField field : type.getFields()) {
-          SeedMarker marker = field.getMarker(SeedMarker.class);
-          if (marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING) {
-            trace(field);
-          }
-        }
-
-        for (JMethod method : type.getMethods()) {
-          SeedMarker marker = method.getMarker(SeedMarker.class);
-          if (marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING) {
-            trace(method);
-          }
-        }
-      }
-
-    }
-
-    @Override
-    public boolean markIfNecessary(@Nonnull JNode node) {
-      synchronized (node) {
-        if (!isMarked(node)) {
-          node.addMarker(new KeepMarker());
-          return true;
-        }
-      }
-      return false;
-    }
-
-    @Override
-    public boolean isMarked(@Nonnull JNode node) {
-      if (node instanceof JDefinedClassOrInterface
-          && ((JDefinedClassOrInterface) node).isExternal()) {
-        return true;
-      } else if (node instanceof JMethod
-          && ((JMethod) node).getEnclosingType().isExternal()) {
-        return true;
-      } else {
-        synchronized (node) {
-          return node.containsMarker(KeepMarker.class);
-        }
-      }
-    }
-
-    @Override
-    protected boolean mustTraceOverridingMethod(@Nonnull JMethod method) {
-      if (method.getEnclosingType().isExternal()) {
-        return true;
-      } else {
-        synchronized (method) {
-          KeepMarker marker = method.getMarker(KeepMarker.class);
-          if (marker != null) {
-            return marker.mustTraceOverridingMethods();
-          }
-        }
-      }
-      return false;
-    }
-
-    @Override
-    protected void setMustTraceOverridingMethods(@Nonnull JMethod method) {
-      synchronized (method) {
-        KeepMarker marker = method.getMarker(KeepMarker.class);
-        if (marker != null) {
-          marker.setMustTraceOverridingMethods(true);
-        } else {
-          assert method.getEnclosingType().isExternal();
-        }
-      }
-    }
-  }
-
-  public static final BooleanPropertyId KEEP_ENCLOSING_METHOD = BooleanPropertyId.create(
-      "jack.shrink.keep.enclosing.method",
-      "Keep the enclosing method of anonymous classes").addDefaultValue(Boolean.FALSE);
+  @Nonnull
+  private final Tracer tracer = new Tracer(new KeeperBrush());
 
   @Override
   public void run(@Nonnull JDefinedClassOrInterface type) throws Exception {
     SeedMarker marker = type.getMarker(SeedMarker.class);
     if (marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING) {
-      Visitor visitor = new Visitor();
-      visitor.trace(type);
+      tracer.trace(type);
     }
   }
 }
diff --git a/jack/src/com/android/jack/shrob/shrink/KeeperBrush.java b/jack/src/com/android/jack/shrob/shrink/KeeperBrush.java
new file mode 100644
index 00000000..5e084c65
--- /dev/null
+++ b/jack/src/com/android/jack/shrob/shrink/KeeperBrush.java
@@ -0,0 +1,120 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.shrob.shrink;
+
+import com.android.jack.analysis.tracer.AbstractTracerBrush;
+import com.android.jack.analysis.tracer.Tracer;
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+import com.android.jack.shrob.seed.SeedMarker;
+import com.android.jack.shrob.spec.KeepModifier;
+import com.android.sched.item.Description;
+import com.android.sched.schedulable.Constraint;
+import com.android.sched.schedulable.Transform;
+import com.android.sched.util.config.HasKeyId;
+import com.android.sched.util.config.ThreadConfig;
+import com.android.sched.util.config.id.BooleanPropertyId;
+
+import javax.annotation.Nonnull;
+
+/**
+ * A {@link Tracer} configuration that marks all classes and members that will be kept when
+ * shrinking.
+ */
+@Description("Marks all classes and members that will be kept when shrinking.")
+@Transform(add = KeepMarker.class)
+@Constraint(need = SeedMarker.class)
+@HasKeyId
+public class KeeperBrush extends AbstractTracerBrush<KeepMarker> {
+
+  @Nonnull
+  public static final BooleanPropertyId KEEP_ENCLOSING_METHOD = BooleanPropertyId.create(
+  "jack.shrink.keep.enclosing.method",
+  "Keep the enclosing method of annonymous classes").addDefaultValue(Boolean.FALSE);
+
+  public KeeperBrush() {
+    super(ThreadConfig.get(KeeperBrush.KEEP_ENCLOSING_METHOD).booleanValue(), KeepMarker.class,
+        SeedMarker.class);
+  }
+
+  @Override
+  protected boolean mustTraceOverridingMethod(@Nonnull JMethod method) {
+    if (method.getEnclosingType().isExternal()) {
+      return true;
+    } else {
+      return super.mustTraceOverridingMethod(method);
+    }
+  }
+
+  @Nonnull
+  @Override
+  protected KeepMarker createMarkerFor(@Nonnull JNode node) {
+    return new KeepMarker();
+  }
+
+  @Override
+  protected boolean isMarked(@Nonnull JNode node) {
+    if (node instanceof JDefinedClassOrInterface
+        && ((JDefinedClassOrInterface) node).isExternal()) {
+      return true;
+    } else if (node instanceof JMethod
+        && ((JMethod) node).getEnclosingType().isExternal()) {
+      return true;
+    } else {
+      return super.isMarked(node);
+    }
+  }
+  @Override
+  public void setMustTraceOverridingMethods(@Nonnull JMethod method) {
+    if (!method.getEnclosingType().isExternal()) {
+      super.setMustTraceOverridingMethods(method);
+    }
+  }
+
+  @Override
+  protected boolean markIfNecessary(@Nonnull JNode node) {
+    if (node instanceof JDefinedClassOrInterface
+        && ((JDefinedClassOrInterface) node).isExternal()) {
+      return false;
+    } else if (node.getParent(JDefinedClassOrInterface.class).isExternal()) {
+      return false;
+    } else {
+      return super.markIfNecessary(node);
+    }
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+    SeedMarker marker = type.getMarker(SeedMarker.class);
+    return marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING;
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JMethod method) {
+    SeedMarker marker = method.getMarker(SeedMarker.class);
+    return marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING;
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JField field) {
+    SeedMarker marker = field.getMarker(SeedMarker.class);
+    return marker != null && marker.getModifier() != KeepModifier.ALLOW_SHRINKING;
+  }
+
+}
diff --git a/jack/src/com/android/jack/shrob/shrink/StructurePrinter.java b/jack/src/com/android/jack/shrob/shrink/ShrinkStructurePrinter.java
index ae4c63ff..8f31e470 100644
--- a/jack/src/com/android/jack/shrob/shrink/StructurePrinter.java
+++ b/jack/src/com/android/jack/shrob/shrink/ShrinkStructurePrinter.java
@@ -16,13 +16,8 @@
 
 package com.android.jack.shrob.shrink;
 
-import com.android.jack.ir.ast.JDefinedClassOrInterface;
-import com.android.jack.ir.ast.JField;
-import com.android.jack.ir.ast.JMethod;
 import com.android.jack.ir.ast.JSession;
-import com.android.jack.ir.ast.JVisitor;
-import com.android.jack.ir.formatter.BinarySignatureFormatter;
-import com.android.jack.ir.formatter.TypeAndMethodFormatter;
+import com.android.jack.util.StructurePrinter;
 import com.android.sched.item.Description;
 import com.android.sched.schedulable.Produce;
 import com.android.sched.schedulable.RunnableSchedulable;
@@ -45,7 +40,7 @@ import javax.annotation.Nonnull;
 @HasKeyId
 @Description("lists all members and types")
 @Produce(StructurePrinting.class)
-public class StructurePrinter implements RunnableSchedulable<JSession> {
+public class ShrinkStructurePrinter implements RunnableSchedulable<JSession> {
 
   @Nonnull
   public static final BooleanPropertyId STRUCTURE_PRINTING = BooleanPropertyId.create(
@@ -59,8 +54,6 @@ public class StructurePrinter implements RunnableSchedulable<JSession> {
       new OutputStreamCodec(Existence.MAY_EXIST).allowStandard())
       .addDefaultValue("-").requiredIf(STRUCTURE_PRINTING.getValue().isTrue());
 
-  private static final TypeAndMethodFormatter formatter = BinarySignatureFormatter.getFormatter();
-
   static class WriteException extends RuntimeException {
 
     private static final long serialVersionUID = 1L;
@@ -85,38 +78,14 @@ public class StructurePrinter implements RunnableSchedulable<JSession> {
   @Nonnull
   private final PrintStream stream;
 
-  public StructurePrinter() {
+  public ShrinkStructurePrinter() {
     stream = ThreadConfig.get(STRUCTURE_PRINTING_FILE).getPrintStream();
   }
 
-  private class Visitor extends JVisitor {
-
-    @Override
-    public boolean visit(@Nonnull JDefinedClassOrInterface type) {
-      stream.print(formatter.getName(type));
-      stream.println(":");
-      return true;
-    }
-
-    @Override
-    public boolean visit(@Nonnull JField field) {
-      stream.print(formatter.getName(field.getType()));
-      stream.print(" ");
-      stream.println(field.getName());
-      return false;
-    }
-
-    @Override
-    public boolean visit(@Nonnull JMethod method) {
-      stream.println(formatter.getName(method));
-      return false;
-    }
-  }
-
   @Override
   public void run(@Nonnull JSession t) throws Exception {
     try {
-      Visitor visitor = new Visitor();
+      StructurePrinter visitor = new StructurePrinter(stream);
       visitor.accept(t.getTypesToEmit());
     } finally {
       stream.close();
diff --git a/jack/src/com/android/jack/shrob/shrink/remover/TypeShrinkMarkerRemover.java b/jack/src/com/android/jack/shrob/shrink/remover/TypeShrinkMarkerRemover.java
index f50c02a9..449c9615 100644
--- a/jack/src/com/android/jack/shrob/shrink/remover/TypeShrinkMarkerRemover.java
+++ b/jack/src/com/android/jack/shrob/shrink/remover/TypeShrinkMarkerRemover.java
@@ -16,8 +16,8 @@
 
 package com.android.jack.shrob.shrink.remover;
 
+import com.android.jack.analysis.tracer.ExtendingOrImplementingClassMarker;
 import com.android.jack.ir.ast.JDefinedClassOrInterface;
-import com.android.jack.shrob.shrink.ExtendingOrImplementingClassMarker;
 import com.android.jack.shrob.shrink.KeepMarker;
 import com.android.sched.item.Description;
 import com.android.sched.schedulable.RunnableSchedulable;
diff --git a/jack/src/com/android/jack/util/MarkedStructurePrinter.java b/jack/src/com/android/jack/util/MarkedStructurePrinter.java
new file mode 100644
index 00000000..66dd11d9
--- /dev/null
+++ b/jack/src/com/android/jack/util/MarkedStructurePrinter.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.util;
+
+import com.android.jack.ir.ast.JNode;
+import com.android.sched.marker.Marker;
+
+import java.io.PrintStream;
+
+import javax.annotation.Nonnull;
+
+/**
+ * Print structure of JNode(s) marked by a given marker.
+ */
+public class MarkedStructurePrinter extends StructurePrinter {
+
+  @Nonnull
+  private final Class<? extends Marker> marker;
+
+  public MarkedStructurePrinter(@Nonnull PrintStream out, @Nonnull Class<? extends Marker> marker) {
+    super(out);
+    this.marker = marker;
+  }
+
+  @Override
+  protected boolean acceptFilter(@Nonnull JNode node) {
+    return node.containsMarker(marker);
+  }
+
+}
diff --git a/jack/src/com/android/jack/util/StructurePrinter.java b/jack/src/com/android/jack/util/StructurePrinter.java
new file mode 100644
index 00000000..cb5db0b8
--- /dev/null
+++ b/jack/src/com/android/jack/util/StructurePrinter.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.util;
+
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+import com.android.jack.ir.ast.JVisitor;
+import com.android.jack.ir.formatter.BinarySignatureFormatter;
+import com.android.jack.ir.formatter.TypeAndMethodFormatter;
+
+import java.io.PrintStream;
+
+import javax.annotation.Nonnull;
+
+/**
+ * Prints the structure of visited JNode(s) accepted by a filter.
+ */
+public class StructurePrinter extends JVisitor {
+
+  @Nonnull
+  private static final TypeAndMethodFormatter formatter = BinarySignatureFormatter.getFormatter();
+
+  @Nonnull
+  private final PrintStream stream;
+
+  public StructurePrinter(@Nonnull PrintStream out) {
+    this.stream = out;
+  }
+
+  @Override
+  public boolean visit(@Nonnull JDefinedClassOrInterface type) {
+    if (acceptFilter(type)) {
+      stream.print(formatter.getName(type));
+      stream.println(":");
+      return true;
+    } else {
+      return false;
+    }
+  }
+
+  @Override
+  public boolean visit(@Nonnull JField field) {
+    if (acceptFilter(field)) {
+      stream.print(formatter.getName(field.getType()));
+      stream.print(" ");
+      stream.println(field.getName());
+    }
+    return false;
+  }
+
+  @Override
+  public boolean visit(@Nonnull JMethod method) {
+    if (acceptFilter(method)) {
+      stream.println(formatter.getName(method));
+    }
+    return false;
+  }
+
+  protected boolean acceptFilter(@Nonnull JDefinedClassOrInterface type) {
+    return acceptFilter((JNode) type);
+  }
+
+  protected boolean acceptFilter(@Nonnull JField field) {
+    return acceptFilter((JNode) field);
+  }
+
+  protected boolean acceptFilter(@Nonnull JMethod method) {
+    return acceptFilter((JNode) method);
+  }
+  /**
+   * @param node structure node, ie class interface or member.
+   */
+  protected boolean acceptFilter(@Nonnull JNode node) {
+    return true;
+  }
+}
diff --git a/jack/tests/com/android/jack/AllTests.java b/jack/tests/com/android/jack/AllTests.java
index de4abfa1..06163651 100644
--- a/jack/tests/com/android/jack/AllTests.java
+++ b/jack/tests/com/android/jack/AllTests.java
@@ -25,6 +25,7 @@ import com.android.jack.jayce.v0002.io.EscapeStringTest;
 import com.android.jack.optimizations.ExpressionSimplifierTest;
 import com.android.jack.optimizations.UselessVariableCopyTest;
 import com.android.jack.tools.merger.MergerAllTests;
+import com.android.jack.tracer.TracingTest;
 import com.android.jack.transformations.ast.string.StringSplittingTest;
 import com.android.jack.transformations.cast.UselessCastRemoverTest;
 import com.android.jack.transformations.flow.CompileFlowTest;
@@ -107,6 +108,7 @@ import org.junit.runners.Suite.SuiteClasses;
     UselessCastRemoverTest.class,
     UselessVariableCopyTest.class,
     WithPhantomTest.class,
-    ClasspathTest.class})
+    ClasspathTest.class,
+    TracingTest.class})
 public class AllTests {
 }
diff --git a/jack/tests/com/android/jack/tracer/MultiMarkedStructurePrinter.java b/jack/tests/com/android/jack/tracer/MultiMarkedStructurePrinter.java
new file mode 100644
index 00000000..fb22cf0a
--- /dev/null
+++ b/jack/tests/com/android/jack/tracer/MultiMarkedStructurePrinter.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.tracer;
+
+import com.android.jack.ir.ast.JNode;
+import com.android.jack.util.StructurePrinter;
+
+import java.io.PrintStream;
+
+import javax.annotation.Nonnull;
+
+public class MultiMarkedStructurePrinter extends StructurePrinter {
+
+  private final int id;
+
+  public MultiMarkedStructurePrinter(@Nonnull PrintStream out, int id) {
+    super(out);
+    this.id = id;
+  }
+
+  @Override
+  protected boolean acceptFilter(@Nonnull JNode node) {
+    MultiTracerMarker marker = node.getMarker(MultiTracerMarker.class);
+    if (marker != null) {
+      return marker.isSet(id);
+    }
+    return false;
+  }
+
+}
diff --git a/jack/tests/com/android/jack/tracer/MultiTracerBrush.java b/jack/tests/com/android/jack/tracer/MultiTracerBrush.java
new file mode 100644
index 00000000..bc6fdbd6
--- /dev/null
+++ b/jack/tests/com/android/jack/tracer/MultiTracerBrush.java
@@ -0,0 +1,217 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.tracer;
+
+import com.android.jack.analysis.tracer.TracerBrush;
+import com.android.jack.ir.ast.HasName;
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JField;
+import com.android.jack.ir.ast.JMethod;
+import com.android.jack.ir.ast.JNode;
+
+import javax.annotation.Nonnull;
+
+public class MultiTracerBrush implements TracerBrush {
+
+  private static final long DISTINCT_FORCED_MARKED_KEY = 17;
+
+  private static final long COMMON_FORCED_MARKED_KEY = 13;
+
+  private static final long DISTINCT_SEED_KEY = 11;
+
+  private static final long COMMON_SEED_KEY = 5;
+
+  private final boolean traceEnclosingMethod;
+
+  private final boolean traceExternal = true;
+
+  private final int id;
+
+  private final int seed;
+
+  public MultiTracerBrush(int id, int seed, boolean traceEnclosingMethod) {
+    this.id = id;
+    this.seed = seed;
+    this.traceEnclosingMethod = traceEnclosingMethod;
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JDefinedClassOrInterface type) {
+    if (type.isExternal()) {
+      return false;
+    }
+    return markIfNecessary(type);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JDefinedClassOrInterface type) {
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JMethod method) {
+    if (method.isExternal()) {
+      return false;
+    }
+    return markIfNecessary(method);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JMethod method) {
+  }
+
+  @Override
+  public boolean startTrace(@Nonnull JField field) {
+    if (field.isExternal()) {
+      return false;
+    }
+    return markIfNecessary(field);
+  }
+
+  @Override
+  public void endTrace(@Nonnull JField field) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+    return isSeed(type);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JDefinedClassOrInterface type) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JMethod method) {
+    return isSeed(method);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JMethod method) {
+  }
+
+  @Override
+  public boolean startTraceSeed(@Nonnull JField field) {
+    return isSeed(field);
+  }
+
+  @Override
+  public void endTraceSeed(@Nonnull JField field) {
+  }
+
+  @Override
+  public boolean startTraceOverridingMethod(@Nonnull JMethod method) {
+    return traceMarked(method) && mustTraceOverridingMethod(method);
+  }
+
+  @Override
+  public void endTraceOverridingMethod(@Nonnull JMethod method) {
+  }
+
+  @Override
+  public boolean traceMarked(@Nonnull JNode node) {
+    if (node instanceof JDefinedClassOrInterface
+        && ((JDefinedClassOrInterface) node).isExternal()) {
+      return traceExternal;
+    } else if (node instanceof JMethod
+        && ((JMethod) node).getEnclosingType().isExternal()) {
+      return traceExternal;
+    } else if (node instanceof JField
+        && ((JField) node).getEnclosingType().isExternal()) {
+      return traceExternal;
+    }
+    return isMarked(node);
+  }
+
+  @Override
+  public void endTraceMarked(@Nonnull JNode node) {
+  }
+
+
+  protected boolean markIfNecessary(@Nonnull JNode node) {
+    if (isForcedMark((HasName) node)) {
+      return false;
+    }
+    synchronized (node) {
+      MultiTracerMarker marker = node.getMarker(MultiTracerMarker.class);
+      if (marker == null) {
+        marker = new MultiTracerMarker();
+        node.addMarker(marker);
+      }
+      if (!marker.isSet(id)) {
+        marker.set(id);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  protected boolean isMarked(@Nonnull JNode node) {
+    if (isForcedMark((HasName) node)) {
+      return true;
+    }
+    synchronized (node) {
+      MultiTracerMarker marker = node.getMarker(MultiTracerMarker.class);
+      if (marker != null) {
+        return marker.isSet(id);
+      }
+    }
+    return false;
+  }
+
+  protected boolean isSeed(@Nonnull HasName node) {
+    return (node.getName().hashCode() + seed) != 0
+        && ((((node.getName().hashCode() + seed) % DISTINCT_SEED_KEY) == 0L)
+            || (((node.getName().hashCode()) % COMMON_SEED_KEY) == 0L));
+  }
+
+  protected boolean isForcedMark(@Nonnull HasName node) {
+    return (node.getName().hashCode() + seed) != 0
+        && ((((node.getName().hashCode() + seed) % DISTINCT_FORCED_MARKED_KEY) == 0L)
+            || (((node.getName().hashCode()) % COMMON_FORCED_MARKED_KEY) == 0L));
+  }
+
+  protected boolean mustTraceOverridingMethod(@Nonnull JMethod method) {
+    synchronized (method) {
+      MultiTracerMarker marker = method.getMarker(MultiTracerMarker.class);
+      if (marker != null) {
+        return marker.mustTraceOverridingMethods(id);
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public void setMustTraceOverridingMethods(@Nonnull JMethod method) {
+    if (!isForcedMark(method)) {
+      synchronized (method) {
+        MultiTracerMarker marker = method.getMarker(MultiTracerMarker.class);
+        assert marker != null && marker.isSet(id);
+        marker.setMustTraceOverridingMethods(id, true);
+      }
+    }
+  }
+
+  @Override
+  public boolean startTraceEnclosingMethod() {
+    return traceEnclosingMethod;
+  }
+
+  @Override
+  public void endTraceEnclosingMethod() {
+  }
+
+}
diff --git a/jack/tests/com/android/jack/tracer/MultiTracerMarker.java b/jack/tests/com/android/jack/tracer/MultiTracerMarker.java
new file mode 100644
index 00000000..abbb99f6
--- /dev/null
+++ b/jack/tests/com/android/jack/tracer/MultiTracerMarker.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.tracer;
+
+import com.android.jack.ir.ast.JNode;
+import com.android.sched.item.Description;
+import com.android.sched.marker.Marker;
+import com.android.sched.marker.ValidOn;
+
+import java.util.BitSet;
+
+import javax.annotation.Nonnull;
+
+@Description("Marker for tests about Multiple tracing")
+@ValidOn(JNode.class)
+public class MultiTracerMarker implements Marker {
+
+  @Nonnull
+  private final BitSet set = new BitSet();
+
+  @Nonnull
+  private final BitSet mustTraceOverridingMethods = new BitSet();
+
+  public void setMustTraceOverridingMethods(int id, boolean mustTraceOverridingMethods) {
+    this.mustTraceOverridingMethods.set(id, mustTraceOverridingMethods);
+  }
+
+  public boolean mustTraceOverridingMethods(int id) {
+    return mustTraceOverridingMethods.get(id);
+  }
+
+  public boolean isSet(int id) {
+    return set.get(id);
+  }
+
+  public void set(int id) {
+    set.set(id);
+  }
+
+  @Override
+  @Nonnull
+  public Marker cloneIfNeeded() {
+    return this;
+  }
+}
diff --git a/jack/tests/com/android/jack/tracer/TracingTest.java b/jack/tests/com/android/jack/tracer/TracingTest.java
new file mode 100644
index 00000000..b472c97b
--- /dev/null
+++ b/jack/tests/com/android/jack/tracer/TracingTest.java
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.jack.tracer;
+
+import com.android.jack.Options;
+import com.android.jack.TestTools;
+import com.android.jack.analysis.tracer.ComposedTracerBrush;
+import com.android.jack.analysis.tracer.ExtendingOrImplementingClassFinder;
+import com.android.jack.analysis.tracer.Tracer;
+import com.android.jack.analysis.tracer.TracerBrush;
+import com.android.jack.ir.ast.JDefinedClassOrInterface;
+import com.android.jack.ir.ast.JSession;
+import com.android.sched.util.RunnableHooks;
+
+import junit.framework.Assert;
+
+import org.junit.Test;
+
+import java.io.ByteArrayOutputStream;
+import java.io.File;
+import java.io.PrintStream;
+
+public class TracingTest {
+
+  private static final int NB_TRACE = 7;
+
+  @Test
+  public void testWithShrob001() throws Exception {
+    doTest(TestTools.getJackTestsWithJackFolder("shrob/test001"));
+  }
+
+  @Test
+  public void testWithShrob016() throws Exception {
+    doTest(TestTools.getJackTestsWithJackFolder("shrob/test016"));
+  }
+
+  @Test
+  public void testWithAnnotation001() throws Exception {
+    doTest(TestTools.getJackTestsWithJackFolder("annotation/test001"));
+  }
+
+  @Test
+  public void testWithFlowLoop() throws Exception {
+    doTest(TestTools.getJackTestsWithJackFolder("flow/loop"));
+  }
+
+  public void doTest(File fileOrSourceList) throws Exception {
+    Options options =
+        TestTools.buildCommandLineArgs(fileOrSourceList);
+    RunnableHooks hooks = new RunnableHooks();
+    try {
+      JSession session = TestTools.buildSession(options, hooks);
+      ExtendingOrImplementingClassFinder hierachyFinder = new ExtendingOrImplementingClassFinder();
+
+      TracerBrush[] brushForComposed = new TracerBrush[NB_TRACE];
+      Tracer[] singleTracers = new Tracer[NB_TRACE];
+      for (int i = 0; i < NB_TRACE; i++) {
+        brushForComposed[i] = new MultiTracerBrush(i, i, false);
+        singleTracers[i] = new Tracer(new MultiTracerBrush(NB_TRACE + i, i, false));
+      }
+
+      TracerBrush brush = new ComposedTracerBrush(brushForComposed);
+      Tracer tracer = new Tracer(brush);
+
+      for (JDefinedClassOrInterface jdcoi : session.getTypesToEmit()) {
+        hierachyFinder.run(jdcoi);
+      }
+
+      for (JDefinedClassOrInterface jdcoi : session.getTypesToEmit()) {
+        tracer.run(jdcoi);
+        for (int i = 0; i < singleTracers.length; i++) {
+          singleTracers[i].run(jdcoi);
+        }
+      }
+
+      for (int i = 0; i < NB_TRACE; i++) {
+        ByteArrayOutputStream refOut = new ByteArrayOutputStream();
+        ByteArrayOutputStream compOut = new ByteArrayOutputStream();
+        MultiMarkedStructurePrinter refPrinter = new MultiMarkedStructurePrinter(
+            new PrintStream(refOut), NB_TRACE + i);
+        MultiMarkedStructurePrinter mdPrinter = new MultiMarkedStructurePrinter(
+            new PrintStream(compOut), i);
+
+        refPrinter.accept(session);
+        mdPrinter.accept(session);
+
+        Assert.assertEquals(refOut.toString(), compOut.toString());
+      }
+    } finally {
+      hooks.runHooks();
+    }
+
+  }
+
+}