sclass MetaTransformer {
  sinterface StructureHandler {
    default O transform(O o, IF1 recurse) { null; }
    void visit(O o, IVF1 recurse);
  }
  
  L<StructureHandler> structureHandlers;
  //bool keepUnknown; // assume true for now
  Set seen; // initialize to identityHashSet() if you want to check for cycles
  
  *() {}
  *(StructureHandler... handlers) { structureHandlers = asList(handlers); }
  
  void addStructureHandler aka add(StructureHandler sh) {
    structureHandlers.add(sh);
  }
  
  // if f returns null, go through structure
  // if f returns an object, do not recurse into it
  // TODO: honor seen
  O transform(IF1 f, O o) {
    ping();
    O x = f.get(o);
    ifdef MetaTransformer_debug
      printVars_str("MetaTransformer.transform", +f, +o, +x);
    endifdef
    if (x != null) ret x;
    
    IF1 recurse = liftFunction(f);
    fOr (StructureHandler h : structureHandlers) {
      ping();
      ifdef MetaTransformer_debug
        print("Calling structure handler " + h + " on " + className(o));
      endifdef
      try object h.transform(o, recurse);
    }
    
    //ret keepUnknown ? o : null;
    ret o;
  }
  
  // transform without result
  void visit(IVF1 f, O o) {
    ping();
    if (o == null) ret;
    if (seen != null && !seen.add(o)) ret;
    f.get(o);
    
    fOr (StructureHandler h : structureHandlers) {
      ping();
      ifdef MetaTransformer_debug
        print("Calling structure handler " + h + " on " + className(o));
      endifdef
      IVF1 recurse = x -> {
        markPointer(o, x);
        visit(f, x);
      };
      h.visit(o, recurse);
    }
  }
  
  void visit_vstack(IVF1 f, O o) {
    vstackCompute(new visit_vstackComputable(f, o));
  }
  
  record visit_vstackComputable(IVF1 f, O o) extends VStackComputableWithStep {
    void step(VStack stack) {
      if (step == 0) {
        ping();
        if (o == null) ret with stack.ret();
        step++;
      }
      
      if (step == 1) {
        if (seen != null && !seen.add(o)) ret with stack.ret();
        ++step;
      }
      
      if (step == 2) {
        f.get(o);
        ++step;
      }
      
      stack.replace(new ForEach_vstack<>(structureHandlers, h -> {
        ifdef MetaTransformer_debug
          print("Calling structure handler " + h + " on " + className(o));
        endifdef
        IVF1 recurse = x -> {
          markPointer(o, x);
          stack.call(new visit_vstackComputable(f, x));
        };
        h.visit(o, recurse);
      }));
    }
  }
  
  // lift transformer function to handle structures
  IF1 liftFunction(IF1 f) {
    ret o -> transform(f, o);
  }
  
  // check if any element satisfies a predicate.
  // Note: might even be faster without the cancel point logic
  bool any(IPred<O> pred, O o) {
    new Flag flag;
    withCancelPoint(cp ->
      visit(x -> { if (pred.get(x)) { flag.raise(); cancelTo(cp); } }, o)
    );
    ret flag.isUp();
  }
  
  void addVisitor(IVF1 visitor) {
    if (visitor == null) ret;
    addStructureHandler(new StructureHandler {
      public void visit(O o, IVF1 recurse) {
        visitor.get(o);
      }
    });
  }
  
  void avoidCycles {
    seen = identityHashSet();
  }
  
  swappable void markPointer(O a, O b) {}
}

Began life as a copy of #1027751