参考Scala Parboiled2，如何用C++模板元编程实现协变/逆变行为？

Great question! Parboiled2's use of Scala's variance annotations to encode parser stack transformations is really clever, and translating that to C++ is a fun metaprogramming challenge. Let's break down how to handle both covariance and contravariance, starting with the easier one before diving into the tricky contravariant case.

First: Recap Parboiled2's Rule Type Logic #

In Parboiled2, a Rule[I, O] represents a parser that transforms an input stack of type I to an output stack of type O. The variance annotations let the type system safely substitute more specific stack types where a more general one is expected (covariance) or vice versa (contravariance). For example, if I1 is a subtype of I2, a covariant Rule[I1, O] can be used anywhere a Rule[I2, O] is needed. Contravariance would let a Rule[I2, O] stand in for a Rule[I1, O]—useful for parsers that accept more general input stacks.

Covariance in C++: Using Inheritance #

You're right that covariance is straightforward to simulate with C++ class inheritance. Here's a simplified example:

First, define a basic stack type hierarchy (representing different parser stack states):

// Base stack type: general, empty or basic stack state
struct BaseStack {};

// Derived stack: more specific, e.g., has an integer value on top
struct IntStack : BaseStack {};

Our Rule template can use inheritance to enable covariance. We'll make Rule<DerivedIn, Out> inherit from Rule<BaseIn, Out> when DerivedIn is a subtype of BaseIn:

// Primary Rule template
template<typename InStack, typename OutStack>
class Rule {};

// Covariant specialization: DerivedIn is a subtype of BaseIn
template<typename BaseIn, typename DerivedIn, typename OutStack>
requires std::is_base_of_v<BaseIn, DerivedIn>
class Rule<DerivedIn, OutStack> : public Rule<BaseIn, OutStack> {
    // Add parser logic here: e.g., stack manipulation, token matching
};

With this setup, a Rule<IntStack, BaseStack> can be implicitly converted to a Rule<BaseStack, BaseStack>—exactly the covariant behavior you'd get from Parboiled2's Rule[+I].

Contravariance in C++: Implicit Conversions & Template Tricks #

C++ doesn't have built-in contravariance for class templates, but we can simulate it using explicit implicit conversion operators and template constraints. The goal is to let a Rule<BaseIn, OutStack> be used where a Rule<DerivedIn, OutStack> is needed (since DerivedIn is a subtype of BaseIn, this is contravariant behavior).

Approach 1: Implicit Conversion Operators #

Here's how to implement it with conversion operators (using C++20 concepts for safety):

// Primary Rule template with contravariant conversion support
template<typename InStack, typename OutStack>
class Rule {
public:
    // Implicit conversion to Rule<DerivedIn, OutStack> if DerivedIn is a subtype of InStack
    template<typename DerivedIn>
    requires std::is_base_of_v<InStack, DerivedIn>
    operator Rule<DerivedIn, OutStack>() const {
        // Construct the target Rule instance (adjust based on your parser's internal logic)
        return Rule<DerivedIn, OutStack>{};
    }

    // Example pure virtual parser method
    virtual void parse() const = 0;
};

// Concrete rule implementation for BaseStack -> BaseStack
struct BaseToBaseRule : Rule<BaseStack, BaseStack> {
    void parse() const override { /* Logic for parsing from BaseStack */ }
};

Now you can use a BaseToBaseRule (a Rule<BaseStack, BaseStack>) wherever a Rule<IntStack, BaseStack> is needed:

void processIntRule(Rule<IntStack, BaseStack> const& rule) {
    rule.parse();
}

int main() {
    BaseToBaseRule baseRule;
    processIntRule(baseRule); // Works! Implicit conversion via contravariant operator
}

Approach 2: Reverse Inheritance Hierarchy #

Another option is to use reverse inheritance: if we want Rule<BaseIn, Out> to be substitutable for Rule<DerivedIn, Out>, we make Rule<BaseIn, Out> inherit from Rule<DerivedIn, Out> (only when DerivedIn is a subtype of BaseIn). This works because derived classes can be converted to base classes, so reversing the inheritance gives us contravariant substitution.

// Primary Rule template
template<typename InStack, typename OutStack>
class Rule {};

// Contravariant specialization: DerivedIn is a subtype of BaseIn
template<typename BaseIn, typename DerivedIn, typename OutStack>
requires std::is_base_of_v<BaseIn, DerivedIn>
class Rule<BaseIn, OutStack> : public Rule<DerivedIn, OutStack> {
    // Parser logic here
};

This lets Rule<BaseStack, Out> be treated as a Rule<IntStack, Out>—exactly the contravariant behavior you're looking for.

Key Considerations #

• C++20 Concepts: Using requires clauses ensures variance conversions only happen when the subtype relationship is valid, preventing unsafe type substitutions.
• Metaprogramming Libraries: For complex stack transformations (like type lists representing multi-element stacks), libraries like Boost.MPL or Boost.Hana can simplify type-level operations.
• Compile-Time Safety: All these type checks happen at compile time, just like Parboiled2's Scala type system—no runtime overhead, just strict parser behavior enforcement.

内容的提问来源于stack exchange，提问作者gct