2

Sometimes, I use the call stack as a data structure. I use local variables as elements on the stack and use the data member of a class to store the top element. When I use this pattern, I feel like I'm doing something a little naughty!

Here's an example of the pattern. The pattern ensures that break and continue statements jump to the right place even in the presence of nested while, for and switch statements.

class StatementVisitor final : public ast::Visitor {
public:
  void visitFlow(ast::Statement *body, llvm::BasicBlock *brake, llvm::BasicBlock *continoo) {
    // Store the old blocks in local variables and push the new blocks.
    llvm::BasicBlock *oldBreak = std::exchange(breakBlock, brake);
    llvm::BasicBlock *oldContinue = std::exchange(continueBlock, continoo);
    // Traverse a statement that might be a block that might have some
    // break or continue statements in it.
    body->accept(*this);
    // Pop the top blocks and restore the previous blocks
    continueBlock = oldContinue;
    breakBlock = oldBreak;
  }

  void visit(ast::For &four) override {
    // ...
    visitFlow(four.body.get(), doneBlock, incrBlock);
    // ...
  }

  void visit(ast::Break &) override {
    // ...
    funcBdr.ir.CreateBr(breakBlock);
    // ...
  }
  void visit(ast::Continue &) override {
    // ...
    funcBdr.ir.CreateBr(continueBlock);
    // ...
  }

private:
  // the blocks that continue and break statements should jump to
  // these are on the top of the stack
  llvm::BasicBlock *continueBlock;
  llvm::BasicBlock *breakBlock;
  FuncBuilder funcBdr;
};

I could use a std::stack<llvm::BasicBlock *> and I end up with roughly the same amount of code. This pattern probably saves memory and a few heap allocations in std::stack. It's so ingrained in my mind (after using it in two other places) that I think of using this before I even realize that I could use a std::stack.

Should I avoid using this pattern?

5

This is a completely normal pattern for a visitor. Using class fields as the top of a stack that's pushed and popped in the method call chain is a perfectly acceptable solution. It's basically a workaround to the fact that you can't pass extra parameters to a generic visitor.

It's sometimes better to understand it as tracking a visitor's context. If you end up having a lot of state, it might be worth creating a helper to push / pop those values via RAII since you're in C++. You can also consider splitting up your visitor into multiple parts so that you can pass the top of your stack in as a parameter to your new object. That might be desirable if immutability is a concern for your code.

  • 2
    I wasn't expecting an answer to say "This is a completely normal pattern for a visitor". This gives me a lot of reassurance. "it might be worth creating a helper to push / pop those values via RAII". I hadn't thought of that! That sounds like a pretty cool idea. I think I'm going to try that. – Kerndog73 Dec 21 '18 at 7:48
  • Yeah, here's a real-world example in the clang source code. The pretty printer tracks the indentation level in the same way as in your question. I've personally written multiple compilers that include this strategy in one way or another. – Alex Reinking Dec 21 '18 at 8:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.