Normalize types at compile time

This also fix the normalization algorithm:
 - Some 'const' after pointers were not removed as they should.
 - No need to keep the space in '> >' and '< :' in C++11 anymore
 - Fix normalization of 'long unsigned int' and similar

Change-Id: I2b72f0fede96c1063e7b155d9f25a85fccfc7bf9
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

4 files changed, 360 insertions, 208 deletions

diff --git a/src/corelib/kernel/qmetaobject.cpp b/src/corelib/kernel/qmetaobject.cpp
index f4d0a88529..62de104c30 100644
--- a/src/corelib/kernel/qmetaobject.cpp
+++ b/src/corelib/kernel/qmetaobject.cpp
@@ -1315,17 +1315,7 @@ static char *qNormalizeType(char *d, int &templdepth, QByteArray &result)
  */
 QByteArray QMetaObject::normalizedType(const char *type)
 {
-    QByteArray result;
-
-    if (!type || !*type)
-        return result;
-
-    QVarLengthArray<char> stackbuf(qstrlen(type) + 1);
-    qRemoveWhitespace(type, stackbuf.data());
-    int templdepth = 0;
-    qNormalizeType(stackbuf.data(), templdepth, result);
-
-    return result;
+    return normalizeTypeInternal(type, type + qstrlen(type));
 }
 
 /*!
diff --git a/src/corelib/kernel/qmetaobject_moc_p.h b/src/corelib/kernel/qmetaobject_moc_p.h
index 471e43f85b..9770d9c576 100644
--- a/src/corelib/kernel/qmetaobject_moc_p.h
+++ b/src/corelib/kernel/qmetaobject_moc_p.h
@@ -52,170 +52,19 @@
 // We mean it.
 //
 
-#include <QtCore/private/qglobal_p.h>
+#include <QtCore/qbytearray.h>
 
 QT_BEGIN_NAMESPACE
 
 // This function is shared with moc.cpp. This file should be included where needed.
-static QByteArray normalizeTypeInternal(const char *t, const char *e, bool fixScope = false, bool adjustConst = true)
+static QByteArray normalizeTypeInternal(const char *t, const char *e)
 {
-    int len = e - t;
-    /*
-      Convert 'char const *' into 'const char *'. Start at index 1,
-      not 0, because 'const char *' is already OK.
-    */
-    QByteArray constbuf;
-    for (int i = 1; i < len; i++) {
-        if ( t[i] == 'c'
-             && strncmp(t + i + 1, "onst", 4) == 0
-             && (i + 5 >= len || !is_ident_char(t[i + 5]))
-             && !is_ident_char(t[i-1])
-             ) {
-            constbuf = QByteArray(t, len);
-            if (is_space(t[i-1]))
-                constbuf.remove(i-1, 6);
-            else
-                constbuf.remove(i, 5);
-            constbuf.prepend("const ");
-            t = constbuf.data();
-            e = constbuf.data() + constbuf.length();
-            break;
-        }
-        /*
-          We mustn't convert 'char * const *' into 'const char **'
-          and we must beware of 'Bar<const Bla>'.
-        */
-        if (t[i] == '&' || t[i] == '*' ||t[i] == '<')
-            break;
-    }
-    if (adjustConst && e > t + 6 && strncmp("const ", t, 6) == 0) {
-        if (*(e-1) == '&') { // treat const reference as value
-            t += 6;
-            --e;
-        } else if (is_ident_char(*(e-1)) || *(e-1) == '>') { // treat const value as value
-            t += 6;
-        }
-    }
-    QByteArray result;
-    result.reserve(len);
-
-#if 1
-    // consume initial 'const '
-    if (strncmp("const ", t, 6) == 0) {
-        t+= 6;
-        result += "const ";
-    }
-#endif
-
-    // some type substitutions for 'unsigned x'
-    if (strncmp("unsigned", t, 8) == 0) {
-        // make sure "unsigned" is an isolated word before making substitutions
-        if (!t[8] || !is_ident_char(t[8])) {
-            if (strncmp(" int", t+8, 4) == 0) {
-                t += 8+4;
-                result += "uint";
-            } else if (strncmp(" long", t+8, 5) == 0) {
-                if ((strlen(t + 8 + 5) < 4 || strncmp(t + 8 + 5, " int", 4) != 0) // preserve '[unsigned] long int'
-                    && (strlen(t + 8 + 5) < 5 || strncmp(t + 8 + 5, " long", 5) != 0) // preserve '[unsigned] long long'
-                   ) {
-                    t += 8+5;
-                    result += "ulong";
-                }
-            } else if (strncmp(" short", t+8, 6) != 0  // preserve unsigned short
-                && strncmp(" char", t+8, 5) != 0) {    // preserve unsigned char
-                //  treat rest (unsigned) as uint
-                t += 8;
-                result += "uint";
-            }
-        }
-    } else {
-        // discard 'struct', 'class', and 'enum'; they are optional
-        // and we don't want them in the normalized signature
-        struct {
-            const char *keyword;
-            int len;
-        } optional[] = {
-            { "struct ", 7 },
-            { "class ", 6 },
-            { "enum ", 5 },
-            { nullptr, 0 }
-        };
-        int i = 0;
-        do {
-            if (strncmp(optional[i].keyword, t, optional[i].len) == 0) {
-                t += optional[i].len;
-                break;
-            }
-        } while (optional[++i].keyword != nullptr);
-    }
-
-    bool star = false;
-    while (t != e) {
-        char c = *t++;
-        if (fixScope && c == ':' && *t == ':' ) {
-            ++t;
-            c = *t++;
-            int i = result.size() - 1;
-            while (i >= 0 && is_ident_char(result.at(i)))
-                --i;
-            result.resize(i + 1);
-        }
-        star = star || c == '*';
-        result += c;
-        if (c == '<') {
-            //template recursion
-            const char* tt = t;
-            int templdepth = 1;
-            int scopeDepth = 0;
-            while (t != e) {
-                c = *t++;
-                if (c == '{' || c == '(' || c == '[')
-                    ++scopeDepth;
-                if (c == '}' || c == ')' || c == ']')
-                    --scopeDepth;
-                if (scopeDepth == 0) {
-                    if (c == '<')
-                        ++templdepth;
-                    if (c == '>')
-                        --templdepth;
-                    if (templdepth == 0 || (templdepth == 1 && c == ',')) {
-                        result += normalizeTypeInternal(tt, t-1, fixScope, false);
-                        result += c;
-                        if (templdepth == 0) {
-                            if (*t == '>')
-                                result += ' '; // avoid >>
-                            break;
-                        }
-                        tt = t;
-                    }
-                }
-            }
-        }
-
-        // cv qualifers can appear after the type as well
-        if (!is_ident_char(c) && t != e && (e - t >= 5 && strncmp("const", t, 5) == 0)
-            && (e - t == 5 || !is_ident_char(t[5]))) {
-            t += 5;
-            while (t != e && is_space(*t))
-                ++t;
-            if (adjustConst && t != e && *t == '&') {
-                // treat const ref as value
-                ++t;
-            } else if (adjustConst && !star) {
-                // treat const as value
-            } else if (!star) {
-                // move const to the front (but not if const comes after a *)
-                result.prepend("const ");
-            } else {
-                // keep const after a *
-                result += "const";
-            }
-        }
-    }
-
-    // Qt 5 compatibility, make sure we use the correct type name for QList
-    result.replace("QList<", "QVector<");
-
+    int len = QtPrivate::qNormalizeType(t, e, nullptr);
+    if (len == 0)
+        return QByteArray();
+    QByteArray result(len, Qt::Uninitialized);
+    len = QtPrivate::qNormalizeType(t, e, result.data());
+    Q_ASSERT(len == result.size());
     return result;
 }
 
diff --git a/src/corelib/kernel/qmetatype.h b/src/corelib/kernel/qmetatype.h
index b89f5cff00..7ee6a2662d 100644
--- a/src/corelib/kernel/qmetatype.h
+++ b/src/corelib/kernel/qmetatype.h
@@ -50,8 +50,9 @@
 #ifndef QT_NO_QOBJECT
 #include <QtCore/qobjectdefs.h>
 #endif
-#include <new>
 
+#include <array>
+#include <new>
 #include <vector>
 #include <list>
 #include <map>
@@ -1741,17 +1742,14 @@ namespace QtPrivate {
 }
 
 template <typename T>
-int qRegisterNormalizedMetaType(const QT_PREPEND_NAMESPACE(QByteArray) &_normalizedTypeName
+int qRegisterNormalizedMetaType(const QT_PREPEND_NAMESPACE(QByteArray) &normalizedTypeName
 #ifndef Q_CLANG_QDOC
     , T * = 0
     , typename QtPrivate::MetaTypeDefinedHelper<T, QMetaTypeId2<T>::Defined && !QMetaTypeId2<T>::IsBuiltIn>::DefinedType  = QtPrivate::MetaTypeDefinedHelper<T, QMetaTypeId2<T>::Defined && !QMetaTypeId2<T>::IsBuiltIn>::Defined
 #endif
 )
 {
-    auto normalizedTypeName = _normalizedTypeName;
 #ifndef QT_NO_QOBJECT
-    // FIXME currently not normalized because we don't do compile time normalization
-    normalizedTypeName = QMetaObject::normalizedType(_normalizedTypeName.constData());
     Q_ASSERT_X(normalizedTypeName == QMetaObject::normalizedType(normalizedTypeName.constData()), "qRegisterNormalizedMetaType", "qRegisterNormalizedMetaType was called with a not normalized type name, please call qRegisterMetaType instead.");
 #endif
 
@@ -2014,8 +2012,6 @@ struct QMetaTypeId< SINGLE_ARG_TEMPLATE<T> > \
         typeName.reserve(int(sizeof(#SINGLE_ARG_TEMPLATE)) + 1 + tNameLen + 1 + 1); \
         typeName.append(#SINGLE_ARG_TEMPLATE, int(sizeof(#SINGLE_ARG_TEMPLATE)) - 1) \
             .append('<').append(tName, tNameLen); \
-        if (typeName.endsWith('>')) \
-            typeName.append(' '); \
         typeName.append('>'); \
         const int newId = qRegisterNormalizedMetaType< SINGLE_ARG_TEMPLATE<T> >( \
                         typeName, \
@@ -2056,8 +2052,6 @@ struct QMetaTypeId< DOUBLE_ARG_TEMPLATE<T, U> > \
         typeName.reserve(int(sizeof(#DOUBLE_ARG_TEMPLATE)) + 1 + tNameLen + 1 + uNameLen + 1 + 1); \
         typeName.append(#DOUBLE_ARG_TEMPLATE, int(sizeof(#DOUBLE_ARG_TEMPLATE)) - 1) \
             .append('<').append(tName, tNameLen).append(',').append(uName, uNameLen); \
-        if (typeName.endsWith('>')) \
-            typeName.append(' '); \
         typeName.append('>'); \
         const int newId = qRegisterNormalizedMetaType< DOUBLE_ARG_TEMPLATE<T, U> >(\
                         typeName, \
@@ -2284,20 +2278,360 @@ public:
     LegacyRegisterOp legacyRegisterOp;
 };
 
+struct QTypeNormalizer
+{
+    char *output;
+    int len = 0;
+    char last = 0;
+
+private:
+    static constexpr bool is_ident_char(char s)
+    {
+        return ((s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z') || (s >= '0' && s <= '9')
+                || s == '_');
+    }
+    static constexpr bool is_space(char s) { return (s == ' ' || s == '\t' || s == '\n'); }
+    static constexpr bool is_number(char s) { return s >= '0' && s <= '9'; };
+    static constexpr bool starts_with_token(const char *b, const char *e, const char *token,
+                                            bool msvcKw = false)
+    {
+        while (b != e && *token && *b == *token) {
+            b++;
+            token++;
+        }
+        if (*token)
+            return false;
+#ifdef Q_CC_MSVC
+        /// On MSVC, keywords like class or struct are not separated with spaces in constexpr
+        /// context
+        if (msvcKw)
+            return true;
+#endif
+        Q_UNUSED(msvcKw);
+        return b == e || !is_ident_char(*b);
+    }
+    static constexpr bool skipToken(const char *&x, const char *e, const char *token,
+                                    bool msvcKw = false)
+    {
+        if (!starts_with_token(x, e, token, msvcKw))
+            return false;
+        while (*token++)
+            x++;
+        while (x != e && is_space(*x))
+            x++;
+        return true;
+    }
+    static constexpr const char *skipString(const char *x, const char *e)
+    {
+        char delim = *x;
+        x++;
+        while (x != e && *x != delim) {
+            if (*x == '\\') {
+                x++;
+                if (x == e)
+                    return e;
+            }
+            x++;
+        }
+        if (x != e)
+            x++;
+        return x;
+    };
+    static constexpr const char *skipTemplate(const char *x, const char *e, bool stopAtComa = false)
+    {
+        int scopeDepth = 0;
+        int templateDepth = 0;
+        while (x != e) {
+            switch (*x) {
+            case '<':
+                if (!scopeDepth)
+                    templateDepth++;
+                break;
+            case ',':
+                if (stopAtComa && !scopeDepth && !templateDepth)
+                    return x;
+                break;
+            case '>':
+                if (!scopeDepth)
+                    if (--templateDepth < 0)
+                        return x;
+                break;
+            case '(':
+            case '[':
+            case '{':
+                scopeDepth++;
+                break;
+            case '}':
+            case ']':
+            case ')':
+                scopeDepth--;
+                break;
+            case '\'':
+                if (is_number(x[-1]))
+                    break;
+                Q_FALLTHROUGH();
+            case '\"':
+                x = skipString(x, e);
+                continue;
+            }
+            x++;
+        }
+        return x;
+    };
+
+    constexpr void append(char x)
+    {
+        last = x;
+        len++;
+        if (output)
+            *output++ = x;
+    }
+
+    constexpr void appendStr(const char *x)
+    {
+        while (*x)
+            append(*x++);
+    };
+
+public:
+    constexpr int normalizeType(const char *begin, const char *end, bool adjustConst = true)
+    {
+        // Trim spaces
+        while (begin != end && is_space(*begin))
+            begin++;
+        while (begin != end && is_space(*(end - 1)))
+            end--;
+
+        // Convert 'char const *' into 'const char *'. Start at index 1,
+        // not 0, because 'const char *' is already OK.
+        const char *cst = begin + 1;
+        if (*begin == '\'' || *begin == '"')
+            cst = skipString(begin, end);
+        bool seenStar = false;
+        bool hasMiddleConst = false;
+        while (cst < end) {
+            if (*cst == '\"' || (*cst == '\'' && !is_number(cst[-1]))) {
+                cst = skipString(cst, end);
+                if (cst == end)
+                    break;
+            }
+
+            // We mustn't convert 'char * const *' into 'const char **'
+            // and we must beware of 'Bar<const Bla>'.
+            if (*cst == '&' || *cst == '*' || *cst == '[') {
+                seenStar = *cst != '&' || cst != (end - 1);
+                break;
+            }
+            if (*cst == '<') {
+                cst = skipTemplate(cst + 1, end);
+                if (cst == end)
+                    break;
+            }
+            cst++;
+            const char *skipedCst = cst;
+            if (!is_ident_char(*(cst - 1)) && skipToken(skipedCst, end, "const")) {
+                const char *testEnd = end;
+                while (skipedCst < testEnd--) {
+                    if (*testEnd == '*' || *testEnd == '['
+                        || (*testEnd == '&' && testEnd != (end - 1))) {
+                        seenStar = true;
+                        break;
+                    }
+                    if (*testEnd == '>')
+                        break;
+                }
+                if (adjustConst && !seenStar) {
+                    if (*(end - 1) == '&')
+                        end--;
+                } else {
+                    appendStr("const ");
+                }
+                normalizeType(begin, cst, false);
+                begin = skipedCst;
+                hasMiddleConst = true;
+                break;
+            }
+        }
+        if (skipToken(begin, end, "const")) {
+            if (adjustConst && !seenStar) {
+                if (*(end - 1) == '&')
+                    end--;
+            } else {
+                appendStr("const ");
+            }
+        }
+        if (seenStar && adjustConst) {
+            const char *e = end;
+            if (*(end - 1) == '&' && *(end - 2) != '&')
+                e--;
+            while (begin != e && is_space(*(e - 1)))
+                e--;
+            const char *token = "tsnoc"; // 'const' reverse, to check if it ends with const
+            while (*token && begin != e && *(--e) == *token++)
+                ;
+            if (!*token && begin != e && !is_ident_char(*(e - 1))) {
+                while (begin != e && is_space(*(e - 1)))
+                    e--;
+                end = e;
+            }
+        }
+
+        // discard 'struct', 'class', and 'enum'; they are optional
+        // and we don't want them in the normalized signature
+        skipToken(begin, end, "struct", true) || skipToken(begin, end, "class", true)
+                || skipToken(begin, end, "enum", true);
+
+#ifdef QT_NAMESPACE
+        const char *nsbeg = begin;
+        if (skipToken(nsbeg, end, QT_STRINGIFY(QT_NAMESPACE)) && nsbeg + 2 < end && nsbeg[0] == ':'
+            && nsbeg[1] == ':') {
+            begin = nsbeg + 2;
+            while (begin != end && is_space(*begin))
+                begin++;
+        }
+#endif
+
+        if (skipToken(begin, end, "QList")) {
+            // Replace QList by QVector
+            appendStr("QVector");
+        }
+        if (!hasMiddleConst) {
+            // Normalize the integer types
+            int numLong = 0;
+            int numSigned = 0;
+            int numUnsigned = 0;
+            int numInt = 0;
+            int numShort = 0;
+            int numChar = 0;
+            while (begin < end) {
+                if (skipToken(begin, end, "long")) {
+                    numLong++;
+                    continue;
+                }
+                if (skipToken(begin, end, "int")) {
+                    numInt++;
+                    continue;
+                }
+                if (skipToken(begin, end, "short")) {
+                    numShort++;
+                    continue;
+                }
+                if (skipToken(begin, end, "unsigned")) {
+                    numUnsigned++;
+                    continue;
+                }
+                if (skipToken(begin, end, "signed")) {
+                    numSigned++;
+                    continue;
+                }
+                if (skipToken(begin, end, "char")) {
+                    numChar++;
+                    continue;
+                }
+                break;
+            }
+            if (numChar || numShort) {
+                if (numSigned && numChar)
+                    appendStr("signed ");
+                if (numUnsigned)
+                    appendStr("unsigned ");
+                if (numChar)
+                    appendStr("char");
+                else
+                    appendStr("short");
+            } else if (numLong) {
+                if (numLong == 1) {
+                    if (numUnsigned)
+                        append('u');
+                    appendStr("long");
+                } else {
+                    if (numUnsigned)
+                        appendStr("unsigned ");
+                    appendStr("long long");
+                }
+            } else if (numUnsigned || numSigned || numInt) {
+                if (numUnsigned)
+                    append('u');
+                appendStr("int");
+            }
+        }
+
+        bool spaceSkiped = true;
+        while (begin != end) {
+            char c = *begin++;
+            if (is_space(c)) {
+                spaceSkiped = true;
+            } else if ((c == '\'' && !is_number(last)) || c == '\"') {
+                begin--;
+                auto x = skipString(begin, end);
+                while (begin < x)
+                    append(*begin++);
+            } else {
+                if (spaceSkiped && is_ident_char(last) && is_ident_char(c))
+                    append(' ');
+                append(c);
+                spaceSkiped = false;
+                if (c == '<') {
+                    do {
+                        // template recursion
+                        const char *tpl = skipTemplate(begin, end, true);
+                        normalizeType(begin, tpl, false);
+                        if (tpl == end)
+                            return len;
+                        append(*tpl);
+                        begin = tpl;
+                    } while (*begin++ == ',');
+                }
+            }
+        }
+        return len;
+    }
+};
+
+// Normalize the type between begin and end, and store the data in the output. Returns the length.
+// The idea is to first run this function with nullptr as output to allocate the output with the
+// size
+constexpr int qNormalizeType(const char *begin, const char *end, char *output)
+{
+    return QTypeNormalizer { output }.normalizeType(begin, end);
+}
+
 template<typename T>
 constexpr auto typenameHelper()
 {
     constexpr auto prefix = sizeof(
-#ifdef Q_CC_CLANG
-        "auto QtPrivate::typenameHelper() [T = ") - 1;
+#ifdef QT_NAMESPACE
+        QT_STRINGIFY(QT_NAMESPACE) "::"
+#endif
+#ifdef Q_CC_MSVC
+        "auto __cdecl QtPrivate::typenameHelper<"
+#elif defined(Q_CC_CLANG)
+        "auto QtPrivate::typenameHelper() [T = "
 #else
-        "constexpr auto QtPrivate::typenameHelper() [with T = ") - 1;
+        "constexpr auto QtPrivate::typenameHelper() [with T = "
 #endif
+        ) - 1;
+#ifdef Q_CC_MSVC
+    constexpr int suffix = sizeof(">(void)");
+#else
     constexpr int suffix = sizeof("]");
-    constexpr int len = sizeof(__PRETTY_FUNCTION__) - prefix - suffix;
+#endif
+
+#if !(defined(Q_CC_GNU) && !defined(Q_CC_INTEL) && !defined(Q_CC_CLANG))
+    constexpr auto func = Q_FUNC_INFO;
+    constexpr const char *begin = func + prefix;
+    constexpr const char *end = func + sizeof(Q_FUNC_INFO) - suffix;
+    constexpr int len = qNormalizeType(begin, end, nullptr);
+#else // GCC < 8.1 did not have Q_FUNC_INFO as constexpr, and GCC 9 has a precompiled header bug
+    auto func = Q_FUNC_INFO;
+    const char *begin = func + prefix;
+    const char *end = func + sizeof(Q_FUNC_INFO) - suffix;
+    // This is an upper bound of the size since the normalized signature should always be smaller
+    // (Unless there is a QList -> QVector change, but that should not happen)
+    constexpr int len = sizeof(Q_FUNC_INFO) - suffix - prefix;
+#endif
     std::array<char, len + 1> result {};
-    for (int i = 0; i < len; ++i)
-        result[i] = __PRETTY_FUNCTION__[prefix + i];
+    qNormalizeType(begin, end, result.data());
     return result;
 }
 
diff --git a/src/tools/moc/moc.cpp b/src/tools/moc/moc.cpp
index 5e2e492f94..b37674320d 100644
--- a/src/tools/moc/moc.cpp
+++ b/src/tools/moc/moc.cpp
@@ -43,30 +43,9 @@
 QT_BEGIN_NAMESPACE
 
 // only moc needs this function
-static QByteArray normalizeType(const QByteArray &ba, bool fixScope = false)
+static QByteArray normalizeType(const QByteArray &ba)
 {
-    const char *s = ba.constData();
-    int len = ba.size();
-    char stackbuf[64];
-    char *buf = (len >= 64 ? new char[len + 1] : stackbuf);
-    char *d = buf;
-    char last = 0;
-    while(*s && is_space(*s))
-        s++;
-    while (*s) {
-        while (*s && !is_space(*s))
-            last = *d++ = *s++;
-        while (*s && is_space(*s))
-            s++;
-        if (*s && ((is_ident_char(*s) && is_ident_char(last))
-                   || ((*s == ':') && (last == '<')))) {
-            last = *d++ = ' ';
-        }
-    }
-    *d = '\0';
-    QByteArray result = normalizeTypeInternal(buf, d, fixScope);
-    if (buf != stackbuf)
-        delete [] buf;
+    QByteArray result = normalizeTypeInternal(ba.constBegin(), ba.constEnd());
     return result;
 }