Can capture-by-reference in expression templates coexist with type deduction?

Question

Expression templates are often used as an optimization technique to avoid the creation of temporary objects. They defer constructing the complete object until the template is used in an assignment or initialization. This finds use in string builders, linear algebra packages, etc.

To avoid expensive copies, the expression template class can capture the bigger arguments by reference. I'll use Qt's QStringBuilder as an example.

It works when the references outlive the expression template:

QString foo = QString("A") + QString("B");
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^
              QStringBuilder<QConcatenable<QString>,
                             QConcatenable<QString>>

The conversion and resolving of the expression template happens at the assignment. The string temporaries outlive the assignment.

Alas, we run into trouble as soon as the expression template type is inferred instead of the target type:

// WORKS
QString foo = []() -> QString { return QString("A") + QString("B"); }();
// FAILS
QString foo = []{ return QString("A") + QString("B"); }();

And also:

auto foo = QString("A") + QString("B");
// foo holds references to strings that don't exist anymore
QString bar = foo; // oops

One solution is for the builder to hold copies of objects. Since QStrings here are implicitly shared, their copying is cheap, although still more expensive than holding a reference. Suppose, though, that the arguments were std::string: you'd definitely not want to copy them unless necessary.

Is there any technique that could be used to detect that a complete template expression is not immediately resolved and must copy the data is thus far only held a reference to?

Note: I'm not asking about any particular existing implementation of expression templates. I only use QStringBuilder as a motivating example. This isn't a Qt question, or an eigen question, etc. The title is the question, pretty much.

Huntsville

Duplicate of #32477134 ? [Not flagged, just asking] – Augustaugusta

@SimonKraemer Since my question didn't get much attention and this one is better phrased and may actually result in an answer I'd leave it as is. – Underpants

@Underpants I just wanted to make sure that this question covers the same issue (or vice versa). – Augustaugusta

This question asks how to design a template expression system to avoid the issue. The other question asks why the problem is there in the first place, and whether it's supposed to be there. Those are different things. – Sos

Maybe I can raise some hope... We can wrap the argument in an object which detects deletion. In your "FAILS" case, the arguments are deleted after initializing foo. This could invoke the creation of a copy of the wrapped object and replace itself within the builder. For this, the wrappers need to be made known with the builder when constructing the builder. I hope you understand my coarse idea... I'm currently experimenting with it and will come back afterwards. – Demonic

@Demonic hvd suggests something similar. I guess that's really the way to do it. – Sos

Indeed my idea was exactly what you described in your comment below his answer. ;) – Demonic

Answer 1

You cannot possibly reliably detect when a reference to an object gets invalidated unless the object somehow gives an indication that it will be invalidated. Nor can you detect in advance whether any particular function will be called for your expression objects, you can only detect that it has been called when it actually gets called.

If your object does provide a way to detect destruction, for instance if it has some event system that tells you about it, then you should be able to modify your expression objects. Instead of just holding a reference to the original data objects, hold a tagged union. Initially, store a pointer to the original data objects. When those data objects are about to be destructed, copy the data and update the tag.

But keep in mind that this doesn't prevent the problem from arising in other ways. An object may have been moved from, for instance, and in that case even though the object is still around, still hasn't been destructed, the data that it holds is no longer meaningful in any reasonable sense of the word.

Ultimately, I think you're trying to use technical means to solve a non-technical problem: you've decided (reasonably, IMO) that you don't want to copy your data when the expressions are constructed, not even when the data objects use COW. You need to either educate your users on the consequences of that decision, or revise your decision.

Magma

This is a good idea. The moving can be signaled in a similar way. This would require cooperation between the template expression objects and the source data - that's precisely the input I've been looking for. – Sos

Building on this idea: One could wrap the some input types with a wrapper whose lifetime would be the same as that of the input. Then one could use non-cooperating source types, such as std::string. The wrapper would track the lifetime of the possibly temporary object and resolve the template before the source objects vanish. The template expression would need to hold the optional resolved value, but I don't think it's that big of an overhead, especially if one uses an optional value type implementation like boost::optional. – Sos

That only works if you make sure the contained std::string is completely inaccessible to outside callers though. If it is accessible, then the outside callers may modify it without you noticing. But on the other hand, if it is not accessible, then this may significantly restrict how and where your wrapper can be used. – Magma

You're right. This scenario wouldn't be supported: std::string foo { "abc" }; auto et = foo + "def"; foo += "!"; return et;. But if you have control over the string's implementation, it can be made to work - and rather easily if the string is implicitly shared, as Qt's string is. – Sos

Answer 2

Is there any technique that could be used to detect that a complete template expression is not immediately resolved and must copy the data is thus far only held a reference to?

That happens mainly when you copy the Builder, so you may manage that in your copy constructor:

struct Expr
{
    explicit Expr(const std::string& s) : s(s) {};

    const std::string& s;
};

struct ExprBuilder
{
    // deleted
    //~~or provide implementation which copy operand (or result)~~ RVO may avoid that fix
    ExprBuilder(const ExprBuilder&) = delete; 
    ExprBuilder& operator = (const ExprBuilder&) = delete;

    ExprBuilder(const Expr& lhs, const Expr& rhs) : lhs(lhs), rhs(rhs) {}

    operator std::string() const { return lhs.s + rhs.s; }

    Expr lhs;
    Expr rhs;
};


ExprBuilder operator + (const Expr& lhs, const Expr& rhs)
{
    return {lhs, rhs};
}

int main() {
    std::string s = Expr("hello") + Expr(" world");

    std::cout << s << std::endl;
    auto builder = Expr("hello") + Expr(" world"); // Use of copy constructor here
    s = builder;
    std::cout << s << std::endl;

    std::string foo =
        []{ return Expr("A") + Expr("B"); } // Use of copy constructor here
        ();
}

but it still fails when you extend life of temporary using const reference

const auto& builder = Expr("hello") + Expr(" world"); // Undetected error here

Bijugate

Part of my motivation was that even copying isn't a sure bet. Due to RVO and NRVO, no copies will be made within a lambda: []{ return Expr("hello") + Expr(" world"); }()... Even if you do have a copy constructor with serious side effects. – Sos

Right point for custom implementation of copy constructor, but as deleted constructors avoid RVO, so this part is still viable. – Bijugate