QStringView Diaries: The Eagle Has Landed

See Chandler Carruth's BoostCon 2013 presentation. Or any other Chandler Carruth presentation ever given :)

TL;DR: Pass by value takes memory out of the picture, simplifying the optimiser's job considerably: values are not forced on the stack with most platform ABIs, and aliasing is not a problem.

Indeed, thanks for the suggestion.

In all brevity: QStringRef cannot reference non-QString-backed data, because it holds a const QString*, a position and a length inside that string. QStringView, otoh, is just a pointer to the character data and a size, and thus agnostic to the owning container. It may, but does not have to be a QString.

So extending QStringRef instead of introducing a new type would keep the Qt API cleaner. Have you considered it?

QStringRef has certain guarantees (it's stable under reallocations of it's string()) that were specifically designed into it. If I were to re-use QStringRef for what QStringView is designed to solve, I would have to do the whole work as an almost-atomic operation between Qt 5 and Qt 6. And I'd still break existing out-of-tree users in the process. I wanted something that was possible to implement here and now, and less disruptive.

QStringView, like std::string_view, expects characters to be contiguous. It cannot represent a rope.

QStringIterator is already ported to QStringView, yes, but since it already sported a (QChar*, QChar*) constructor, you could've passed (and can still pass) begin() and end() of a QStringView even if it wasn't.

A string-view is conceptually similar, if not identical, to the STL design of separating algorithms from containers by having containers provide, and algorithms work with, iterators. A function taking a string-view is an algorithm on characters. The string-view is the iterator pair, and which container the algorithm works on is abstracted. Only, because we're working with a rather restricted set of value types and only contiguous memory, we don't need to write our algorithms as template functions. A normal function taking QStringView will do, because const QChar* is always the iterator.

As for fixing QString: There are many things that I'd like to see fixed in QString, and I've mentioned them in the article. But a string class needs to hold strings of arbitrary size. So it must (eventually) allocate memory, and own it. That makes QString a container and fundamentally different from a string-view.

The traditional isValidIdentifier() is not a total function:

auto id = u"Hello";
if (isValidIdentifier(cast...(id), 15)) // ERROR: precondition violation
                                        // [ptr, len) is not a valid range

And neither is QStringView's constructor taking the same arguments:

auto sv = QStringView{u"Hello", 15}; // ERROR: precondition violation
                                     // [ptr, len) is not a valid range

Consequently, that constructor is not noexcept.

This is subtle, I know: If isValidIdentifier() is ported to QStringView it becomes a total function:

auto id = u"Hello";
if (isValidIdentifier(QStringView(id, 15)) // ERROR: precondition violation
                                           // [ptr, len) is not a valid range
                                           // _while constructing QStringView_!

Crucially, the UB now happens outside the function, in the QStringView constructor, just as in the second example.

If you think there's no difference, consider this: If I have some sanitizer API that would allow me to assert that a [ptr, len) range is valid, I could report the error. In the traditional case, I'd need to detect and report it inside isValidIdentifier() (and in all other such functions). With QStringView, it's detected and reported from the QStringView ctor.

If you think there’s no difference, consider this: If I have some sanitizer API that would allow me to assert that a [ptr, len) range is valid, I could report the error. In the traditional case, I’d need to detect and report it inside isValidIdentifier() (and in all other such functions). With QStringView, it’s detected and reported from the QStringView ctor.

https://codereview.qt-project.org/193707

Yes, I think I see what you're getting at - it makes perfect sense.

I suspect it may just be my lack of experience with QStringView which keeps me from acknowledging that using QStringView actually makes isValidIdentifier a total function. Or maybe it's because my idea of what constitutes a 'precondition' differs from yours (to me, it's a pre-condition of a piece of code which is not currently expressed in the type system but which has to be asserted at runtime).

My understanding is that QStringView itself does not verify that the given range is valid. It also doesn't create a copy of the data. Hence, the precondition on isValidIdentifier is still that a valid range is passed. It's just that instead of passing a starting address and a length, a QStringView is passed - but there's nothing in the type system or in the constructor of QStringView which can enforce that the given QStringView denotes a valid range. I.e. the QStringView constructor still permits constructing invalid ranges, so there is a (wide) range of invalid QStringView objects possible for which isValidIdentifier is not well-defined, and hence partial.

Unfortunately I cannot seem to figure out how to do syntax highlighting in this blog, but to give an example of what I mean: If you consider this function for getting the first character of a string to be partial:

QChar firstCharacter( const QString &s ) {
  return s[0]; // Oops - what if it's an empty string?
}

...then this might be a way to make it a total function, by using the type system and enforcing the precondition in the constructor:

struct NonEmptyString {
  QString value;
  NonEmptyString( const QString &s ) {
    if ( s.isEmpty() ) {
      throw std::logic_error( "empty string passed" );
    }
  }
};

QChar firstCharacter( const NonEmptyString &s ) {
  return s.value[0]; // Fine - no NonEmptyString object ever exists having an empty value member
}

My impression is that QStringView does not give any such guarantees since the behaviour of QStringView's constructor is undefined for empty ranges.

A pre-condition of a function is a condition that needs to be true on the arguments of the function in order for the function to realise its post-conditions. Calling a function without all pre-conditions met is undefined behaviour. You seem to want it have defined behaviour. Here's why that's a fallacy:

Yes, ideally, a precondition would be a predicate in the same language as the function. But that is frequently not possible, or even if it is possible, it's not desirable to check it.

E.g. std::lower_bound(first, last, value, cmp) has the following pre-conditions, which are usually not assertable:

• [first, last) is a valid range

  Not checkable in C++, can be checked with a Valgrind hook for contiguous iterators. Cannot be checked at all for non-contiguous iterators (e.g. QList::iterator)

• [first, last) is sorted according to cmp

  Checkable, but the check is O(N) (and changes the requirements on cmp!) while the functionality is O(logN), so usually not asserted.

• cmp is a strict weak ordering

  Not checkable, unless by exhaustive testing, which is only possible for fixed-size Domain(cmp). If cmp is calling strcmp(), then you've lost.

But even though these are not checkable (or too expensive to check), they're still pre-conditions of the function, and failing to meet them means the function will not reliably meet its post-conditions.

So, the QStringView ctor checks the cheap preconditions, but fails to check the expensive or uncheckable ones. That doesn't mean you're free to create a QStringView with too large size. You're still violating preconditions, and you're still invoking UB.

Did you see https://codereview.qt-project.org/193707 ?

I concur with every word you write, but I feel I'm drawing a different conclusion. You are of course perfectly right when you say that it's frequently not possible (or practical) to assert preconditions in code. std::lower_bound is a good example.

In the same way, the traditional isValidIdentifier function had preconditions which code cannot easily verify (that the given range is valid). And indeed, QStringView inherits this behaviour in that the QStringView has no practical way to verify that the given range is valid. I believe that so far, we're on the same page.

Now, the conclusion I draw from this (and I think this is where we diverge) is that the new, QStringView-based definition of isValidIdentifier is still as easy (or hard) to call correctly as before. The contract is as wide (or narrow) as before - since the function still asserts that the given view denotes a valid range. A QStringView is isomorphic to a char */int tuple, and the set of QStringView objects which violate the precondition is as large as the set of parameter combinations with which the traditional isValidIdentifier function must not be called.

In the same vein, in my understanding, the contract of std::lower_bound would not change if instead of

std::lower_bound(first, last, value, cmp)

it would be declared as e.g.

std::lower_bound(range, value, cmp)

With range being something like

  template <typename Iterator>
  struct Range {
    Iterator start;
    Iterator end;
  };

The contract of std::lower_bound will still include that you have to pass a valid range. It just happens that the range is no longer expressed as two iterators but as a Range object (which does not enforce that the range is valid!).

You pointed out that with the traditional definition of isValidIdentifier "Only certain combinations of the two parameters are allowed". My understanding is that the same holds true if isValidIdentifier is given a QStringView - only certain QStringView objects (those which denote a valid range) are allowed. It would be a very different story if isValidIdentifier was given a real QString, which took a copy of the data.

That's what I meant to express with my NonEmptyString example: by raising an exception in the constructor (and copying the data), it's actually impossible to construct objects which transport empty strings. So the set of possible NonEmptyString is actually smaller than the set of all possible std::string objects, and hence the contract of the firstCharacter function becomes, in your terms, wider when using NonEmptyString.

Regarding https://codereview.qt-project.org/193707 -- yes, I did notice it, but I didn't quite understand what's going on. I'm not too familiar with Valgrind unfortunately.

A QStringView is isomorphic to a char */int tuple, [...]

This is where we disagree, indeed. A QStringView is a new type. It has (const QChar*, qqsize_t) members, yes, but it is not isomorphic to a tuple made out of its data members any more than a QString is isomorphic to a QString::Data*. That's because a C++ class can, and usually does, introduce class invariants. The constructor is responsible for establishing the class invariant, but frequently, if it depends on user-provided arguments, the extent to which it can guarantee that all class invariants have been successfully established is limited. This is where the C++ standard resorts to the phrase "undefined behaviour, no diagnostic required". And a normal C++ class can do the same.

That said, the change I linked attempts to do away with the "no diagnostic" part, by using a Valgrind hook to check, at QStringView construction time, whether the given range contains valid data.

Now, crucially, any function has an implicit pre-condition that its arguments are valid values of the arguments' types. In your definition of a total function, that means such functions cannot have arguments of types that have class invariants. Ok, if that is the definition of a total function then functions taking QStringView are never total, indeed. Neither is a function taking NonEmptyString total, though, since NonEmptyString clearly has class invariants, too.

I just noticed that since the NonEmptyString constructor never actually initializes the value member, the comment in the second firstCharacter definition is very misleading; every NonEmptyString object will have an empty value member. Oops. :-)