containers.cpp 49.9 KB
Newer Older
hjk's avatar
hjk committed
1
/****************************************************************************
2
**
Eike Ziller's avatar
Eike Ziller committed
3 4
** Copyright (C) 2015 The Qt Company Ltd.
** Contact: http://www.qt.io/licensing
5
**
hjk's avatar
hjk committed
6
** This file is part of Qt Creator.
7
**
hjk's avatar
hjk committed
8 9 10 11
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
Eike Ziller's avatar
Eike Ziller committed
12 13
** a written agreement between you and The Qt Company.  For licensing terms and
** conditions see http://www.qt.io/terms-conditions.  For further information
Eike Ziller's avatar
Eike Ziller committed
14
** use the contact form at http://www.qt.io/contact-us.
15 16
**
** GNU Lesser General Public License Usage
hjk's avatar
hjk committed
17
** Alternatively, this file may be used under the terms of the GNU Lesser
Eike Ziller's avatar
Eike Ziller committed
18 19 20 21 22 23
** General Public License version 2.1 or version 3 as published by the Free
** Software Foundation and appearing in the file LICENSE.LGPLv21 and
** LICENSE.LGPLv3 included in the packaging of this file.  Please review the
** following information to ensure the GNU Lesser General Public License
** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
hjk's avatar
hjk committed
24
**
Eike Ziller's avatar
Eike Ziller committed
25 26
** In addition, as a special exception, The Qt Company gives you certain additional
** rights.  These rights are described in The Qt Company LGPL Exception
con's avatar
con committed
27 28
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
hjk's avatar
hjk committed
29
****************************************************************************/
30 31 32 33 34

#include "containers.h"
#include "symbolgroupvalue.h"
#include "symbolgroup.h"
#include "stringutils.h"
35
#include "extensioncontext.h"
36

37
#include <functional>
38
#include <iterator>
39

40
typedef AbstractSymbolGroupNode::AbstractSymbolGroupNodePtrVector AbstractSymbolGroupNodePtrVector;
41 42
typedef std::vector<SymbolGroupValue> SymbolGroupValueVector;
typedef std::vector<int>::size_type VectorIndexType;
43

44 45
// Read a pointer array from debuggee memory (ULONG64/32 according pointer size)
static void *readPointerArray(ULONG64 address, unsigned count, const SymbolGroupValueContext &ctx)
46
{
47 48 49 50 51 52 53 54 55 56
    const unsigned pointerSize = SymbolGroupValue::pointerSize();
    const ULONG allocSize = pointerSize * count;
    ULONG bytesRead = 0;
    void *data = new unsigned char[allocSize];
    const HRESULT hr = ctx.dataspaces->ReadVirtual(address, data, allocSize, &bytesRead);
    if (FAILED(hr) || bytesRead != allocSize) {
        delete [] data;
        return 0;
    }
    return data;
57 58
}

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
template <class UInt>
inline void dumpHexArray(std::ostream &os, const UInt *a, int count)
{
    os << std::showbase << std::hex;
    std::copy(a, a + count, std::ostream_iterator<UInt>(os, ", "));
    os << std::noshowbase << std::dec;
}

static inline void dump32bitPointerArray(std::ostream &os, const void *a, int count)
{
    dumpHexArray(os, reinterpret_cast<const ULONG32 *>(a), count);
}

static inline void dump64bitPointerArray(std::ostream &os, const void *a, int count)
{
    dumpHexArray(os, reinterpret_cast<const ULONG64 *>(a), count);
}

77 78
// Fix the inner type of containers (that is, make it work smoothly with AddSymbol)
// by prefixing it with the module except for well-known types like STL/Qt types
Orgad Shaneh's avatar
Orgad Shaneh committed
79
static inline std::string fixInnerType(const std::string &type,
80
                                       const SymbolGroupValue &container)
81
{
82
    std::string stripped
83
        = SymbolGroupValue::stripConst(SymbolGroupValue::stripClassPrefixes(type));
84 85 86 87 88 89 90

    // Unfortunately the cdb can not handle the vc exclusiv 64 bit integer
    // "__int64" but works fine with "int64", so we have to strip down "__"
    const size_t __int64pos = stripped.find("__int64");
    if (__int64pos != std::string::npos)
        stripped.erase(__int64pos, 2);

91 92 93 94
    const KnownType kt = knownType(stripped, 0);
    // Resolve types unless they are POD or pointers to POD (that is, qualify 'Foo' and 'Foo*')
    const bool needResolve = kt == KT_Unknown || kt ==  KT_PointerType || !(kt & KT_POD_Type);
    const std::string fixed = needResolve ?
95
                SymbolGroupValue::resolveType(stripped, container.context(), container.module()) :
96 97 98 99 100 101 102 103
                stripped;
    if (SymbolGroupValue::verbose) {
        DebugPrint dp;
        dp << "fixInnerType (resolved=" << needResolve << ") '" << type << "' [";
        formatKnownTypeFlags(dp, kt);
        dp << "] -> '" << fixed <<"'\n";
    }
    return fixed;
104 105
}

106 107 108
// Return size from an STL vector (last/first iterators).
static inline int msvcStdVectorSize(const SymbolGroupValue &v)
{
109 110 111
    // MSVC2012 has 2 base classes, MSVC2010 1, MSVC2008 none
    if (const SymbolGroupValue myFirstPtrV = SymbolGroupValue::findMember(v, "_Myfirst")) {
        if (const SymbolGroupValue myLastPtrV = myFirstPtrV.parent()["_Mylast"]) {
112 113 114 115 116 117 118 119
            const ULONG64 firstPtr = myFirstPtrV.pointerValue();
            const ULONG64 lastPtr = myLastPtrV.pointerValue();
            if (!firstPtr || lastPtr < firstPtr)
                return -1;
            if (lastPtr == firstPtr)
                return 0;
            // Subtract the pointers: We need to do the pointer arithmetics ourselves
            // as we get char *pointers.
120
            const std::string innerType = fixInnerType(SymbolGroupValue::stripPointerType(myFirstPtrV.type()), v);
121 122 123 124 125 126 127 128 129
            const size_t size = SymbolGroupValue::sizeOf(innerType.c_str());
            if (size == 0)
                return -1;
            return static_cast<int>((lastPtr - firstPtr) / size);
        }
    }
    return -1;
}

130 131 132 133 134 135 136 137 138 139 140
// Return size of container or -1
int containerSize(KnownType kt, SymbolGroupNode *n, const SymbolGroupValueContext &ctx)
{
    QTC_TRACE_IN
    if ((kt & KT_ContainerType) == 0)
        return -1;
    const int ct = containerSize(kt, SymbolGroupValue(n, ctx));
    QTC_TRACE_OUT
    return ct;
}

141
/*! Determine size of containers \ingroup qtcreatorcdbext */
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
int containerSize(KnownType kt, const SymbolGroupValue &v)
{
    switch (kt) {
    case KT_QStringList:
        if (const SymbolGroupValue base = v[unsigned(0)])
            return containerSize(KT_QList, base);
        break;
    case KT_QList:
        if (const SymbolGroupValue dV = v["d"]) {
            if (const SymbolGroupValue beginV = dV["begin"]) {
                const int begin = beginV.intValue();
                const int end = dV["end"].intValue();
                if (begin >= 0 && end >= begin)
                    return end - begin;
            }
        }
        break;
    case KT_QLinkedList:
    case KT_QHash:
        if (const SymbolGroupValue sizeV = v["d"]["size"])
            return sizeV.intValue();
        break;
164 165 166 167 168 169 170 171 172 173
    case KT_QMap:
    case KT_QVector: {
        // Inheritance from QVectorTypedData, QMapData<> in Qt 5.
        const SymbolGroupValue sizeV =
            QtInfo::get(v.context()).version >= 5 ?
            v["d"][unsigned(0)]["size"] : v["d"]["size"];
        if (sizeV)
            return sizeV.intValue();
    }
        break;
174 175 176 177
    case KT_QMultiHash:
        if (const SymbolGroupValue qHash = v[unsigned(0)])
            return containerSize(KT_QHash, qHash);
        break;
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
    case KT_QQueue:
        if (const SymbolGroupValue qList= v[unsigned(0)])
            return containerSize(KT_QList, qList);
        break;
    case KT_QStack:
        if (const SymbolGroupValue qVector = v[unsigned(0)])
            return containerSize(KT_QVector, qVector);
        break;
    case KT_QSet:
        if (const SymbolGroupValue base = v[unsigned(0)])
            return containerSize(KT_QHash, base);
        break;
    case KT_QMultiMap:
        if (const SymbolGroupValue base = v[unsigned(0)])
            return containerSize(KT_QMap, base);
        break;
194 195 196 197 198 199
    case KT_StdVector:
        return msvcStdVectorSize(v);
    case KT_StdDeque: // MSVC2012 has many base classes, MSVC2010 1, MSVC2008 none
    case KT_StdSet:
    case KT_StdMap:
    case KT_StdMultiMap:
200
    case KT_StdList:
201 202
        if (const SymbolGroupValue size = SymbolGroupValue::findMember(v, "_Mysize"))
            return size.intValue();
203 204 205 206 207
        break;
    case KT_StdStack:
        if (const SymbolGroupValue deque =  v[unsigned(0)])
            return containerSize(KT_StdDeque, deque);
        break;
208 209 210 211 212
    case KT_StdArray: {
        std::string::size_type arraySizeStart = v.type().find(',');
        if (arraySizeStart != std::string::npos) {
            ++arraySizeStart;
            std::string::size_type arraySizeEnd = v.type().find('>', arraySizeStart);
213 214 215 216 217
            if (arraySizeEnd != std::string::npos) {
                int rc = 0;
                if (integerFromString(v.type().substr(arraySizeStart, arraySizeEnd - arraySizeStart), &rc))
                    return rc;
            }
218 219
        }
        break;
220
    }
221 222
    }

223 224 225 226 227 228
    return -1;
}

/* Generate a list of children by invoking the functions to obtain the value
 * and the next link */
template <class ValueFunction, class NextFunction>
229
AbstractSymbolGroupNodePtrVector linkedListChildList(SymbolGroupValue headNode,
230
                                                     unsigned count,
231 232
                                                     ValueFunction valueFunc,
                                                     NextFunction nextFunc)
233
{
234
    AbstractSymbolGroupNodePtrVector rc;
235
    rc.reserve(count);
236
    for (unsigned i = 0; i < count && headNode; i++) {
237
        if (const SymbolGroupValue value = valueFunc(headNode)) {
238
            rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, value.node()));
239 240 241 242 243 244 245 246 247
            headNode = nextFunc(headNode);
        } else {
            break;
        }
    }
    return rc;
}

// Helper function for linkedListChildList that returns a member by name
248 249
class MemberByName : public std::unary_function<const SymbolGroupValue &, SymbolGroupValue>
{
250 251 252 253 254 255 256 257
public:
    explicit MemberByName(const char *name) : m_name(name) {}
    SymbolGroupValue operator()(const SymbolGroupValue &v) { return v[m_name]; }

private:
    const char *m_name;
};

258
// std::list<T>: Skip dummy head node and then a linked list of "_Next", "_Myval".
259
static inline AbstractSymbolGroupNodePtrVector stdListChildList(SymbolGroupNode *n, unsigned count,
260 261
                                                        const SymbolGroupValueContext &ctx)
{
262 263
    if (!count)
        return AbstractSymbolGroupNodePtrVector();
264 265 266 267 268 269
    const SymbolGroupValue head = SymbolGroupValue::findMember(SymbolGroupValue(n, ctx), "_Myhead")["_Next"];
    if (head)
        return linkedListChildList(head, count, MemberByName("_Myval"), MemberByName("_Next"));
    if (SymbolGroupValue::verbose)
        DebugPrint() << "std::list failure: " << head;
    return AbstractSymbolGroupNodePtrVector();
270 271
}

272
static inline AbstractSymbolGroupNodePtrVector stdArrayChildList(SymbolGroupNode *n, unsigned count,
273 274 275 276 277
                                                        const SymbolGroupValueContext &ctx)
{
    AbstractSymbolGroupNodePtrVector rc;
    if (SymbolGroupValue elems = SymbolGroupValue(n, ctx)["_Elems"]) {
        rc.reserve(count);
278
        for (unsigned i = 0; i < count; ++i) {
279 280 281 282 283 284 285 286 287
            if (const SymbolGroupValue value = elems[i])
                rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, value.node()));
            else
                break;
        }
    }
    return rc;
}

288
// QLinkedList<T>: Dummy head node and then a linked list of "n", "t".
289 290
static inline AbstractSymbolGroupNodePtrVector qLinkedListChildList(
        SymbolGroupNode *n, unsigned count, const SymbolGroupValueContext &ctx)
291 292 293 294
{
    if (count)
        if (const SymbolGroupValue head = SymbolGroupValue(n, ctx)["e"]["n"])
            return linkedListChildList(head, count, MemberByName("t"), MemberByName("n"));
295
    return AbstractSymbolGroupNodePtrVector();
296 297
}

298
/* Helper for array-type containers:
299 300
 * Add a series of "*(innertype *)0x (address + n * size)" fake child symbols.
 * for a function generating a sequence of addresses. */
301

302
template <class AddressFunc>
303
AbstractSymbolGroupNodePtrVector arrayChildList(SymbolGroup *sg, AddressFunc addressFunc,
304 305
                                                const std::string &module,
                                                const std::string &innerType,
306
                                                unsigned count)
307
{
308
    AbstractSymbolGroupNodePtrVector rc;
309
    if (!count)
310 311 312
        return rc;
    std::string errorMessage;
    rc.reserve(count);
313
    for (unsigned i = 0; i < count; i++) {
314
        const std::string name = SymbolGroupValue::pointedToSymbolName(addressFunc(), innerType);
315
        if (SymbolGroupNode *child = sg->addSymbol(module, name, std::string(), &errorMessage)) {
316
            rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, child));
317
        } else {
318 319
            if (SymbolGroupValue::verbose)
                DebugPrint() << "addSymbol fails in arrayChildList";
320 321 322
            break;
        }
    }
323 324 325
    if (SymbolGroupValue::verbose)
        DebugPrint() << "arrayChildList '" << innerType << "' count=" << count << " returns "
                     << rc.size() << " elements";
326 327 328
    return rc;
}

329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
// Helper function for arrayChildList() taking a reference to an address and simply generating
// a sequence of address, address + delta, address + 2 * delta...
class AddressSequence
{
public:
    explicit inline AddressSequence(ULONG64 &address, ULONG delta) : m_address(address), m_delta(delta) {}
    inline ULONG64 operator()()
    {
        const ULONG64 rc = m_address;
        m_address += m_delta;
        return rc;
    }

private:
    ULONG64 &m_address;
    const ULONG m_delta;
};

347 348
static inline AbstractSymbolGroupNodePtrVector
    arrayChildList(SymbolGroup *sg, ULONG64 address, const std::string &module,
349
                   const std::string &innerType, unsigned count)
350 351
{
    if (const unsigned innerTypeSize = SymbolGroupValue::sizeOf(innerType.c_str()))
352
        return arrayChildList(sg, AddressSequence(address, innerTypeSize),
353
                              module, innerType, count);
354
    return AbstractSymbolGroupNodePtrVector();
355 356
}

357
// std::vector<T>
358
static inline AbstractSymbolGroupNodePtrVector
359
    stdVectorChildList(SymbolGroupNode *n, unsigned count, const SymbolGroupValueContext &ctx)
360
{
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
    if (!count)
        return AbstractSymbolGroupNodePtrVector();
    // MSVC2012 has 2 base classes, MSVC2010 1, MSVC2008 none
    const SymbolGroupValue vec = SymbolGroupValue(n, ctx);
    SymbolGroupValue myFirst = SymbolGroupValue::findMember(vec, "_Myfirst");
    if (!myFirst)
        return AbstractSymbolGroupNodePtrVector();
    // std::vector<T>: _Myfirst is a pointer of T*. Get address
    // element to obtain address.
    const ULONG64 address = myFirst.pointerValue();
    if (!address)
        return AbstractSymbolGroupNodePtrVector();
    const std::string firstType = myFirst.type();
    const std::string innerType = fixInnerType(SymbolGroupValue::stripPointerType(firstType), vec);
    if (SymbolGroupValue::verbose)
        DebugPrint() << n->name() << " inner type: '" << innerType << "' from '" << firstType << '\'';
    return arrayChildList(n->symbolGroup(), address, n->module(), innerType, count);
378 379
}

380 381 382 383 384
// Helper for std::deque<>: From the array of deque blocks, read out the values.
template<class AddressType>
AbstractSymbolGroupNodePtrVector
    stdDequeChildrenHelper(SymbolGroup *sg,
                           const AddressType *blockArray, ULONG64 blockArraySize,
385
                           const std::string &module,
386
                           const std::string &innerType, ULONG64 innerTypeSize,
387
                           ULONG64 startOffset, ULONG64 dequeSize, unsigned count)
388 389 390 391 392 393
{
    AbstractSymbolGroupNodePtrVector rc;
    rc.reserve(count);
    std::string errorMessage;
    // Determine block number and offset in the block array T[][dequeSize]
    // and create symbol by address.
394
    for (unsigned i = 0; i < count; i++) {
395 396 397 398 399 400 401
        // see <deque>-header: std::deque<T>::iterator::operator*
        const ULONG64 offset = startOffset + i;
        ULONG64 block = offset / dequeSize;
        if (block >= blockArraySize)
            block -= blockArraySize;
        const ULONG64 blockOffset = offset % dequeSize;
        const ULONG64 address = blockArray[block] + innerTypeSize * blockOffset;
402
        if (SymbolGroupNode *n = sg->addSymbol(module, SymbolGroupValue::pointedToSymbolName(address, innerType), std::string(), &errorMessage))
403
            rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, n));
404
        else
405 406 407 408 409 410 411
            return AbstractSymbolGroupNodePtrVector();
    }
    return rc;
}

// std::deque<>
static inline AbstractSymbolGroupNodePtrVector
412
    stdDequeChildList(const SymbolGroupValue &dequeIn, unsigned count)
413 414 415
{
    if (!count)
        return AbstractSymbolGroupNodePtrVector();
416 417 418 419 420 421
    // From MSVC10 on, there is an additional base class, MSVC2012 more.
    const SymbolGroupValue map = SymbolGroupValue::findMember(dequeIn, "_Map");
    if (!map)
        return AbstractSymbolGroupNodePtrVector();
    const SymbolGroupValue deque = map.parent();
    const ULONG64 arrayAddress = map.pointerValue();
422 423
    const int startOffset = deque["_Myoff"].intValue();
    const int mapSize  = deque["_Mapsize"].intValue();
424 425
    if (!arrayAddress || startOffset < 0 || mapSize <= 0)
        return AbstractSymbolGroupNodePtrVector();
426
    const std::vector<std::string> innerTypes = dequeIn.innerTypes();
427 428
    if (innerTypes.empty())
        return AbstractSymbolGroupNodePtrVector();
429
    const std::string innerType = fixInnerType(innerTypes.front(), deque);
430 431
    // Get the deque size (block size) which is an unavailable static member
    // (cf <deque> for the actual expression).
432
    const unsigned innerTypeSize = SymbolGroupValue::sizeOf(innerType.c_str());
433 434 435 436 437
    if (!innerTypeSize)
        return AbstractSymbolGroupNodePtrVector();
    const int dequeSize = innerTypeSize <= 1 ? 16 : innerTypeSize <= 2 ?
                               8 : innerTypeSize <= 4 ? 4 : innerTypeSize <= 8 ? 2 : 1;
    // Read out map array (pointing to the blocks)
438
    void *mapArray = readPointerArray(arrayAddress, mapSize, deque.context());
439 440 441
    if (!mapArray)
        return AbstractSymbolGroupNodePtrVector();
    const AbstractSymbolGroupNodePtrVector rc = SymbolGroupValue::pointerSize() == 8 ?
442
        stdDequeChildrenHelper(deque.node()->symbolGroup(),
443
                               reinterpret_cast<const ULONG64 *>(mapArray), mapSize,
444
                               deque.module(), innerType, innerTypeSize, startOffset, dequeSize, count) :
445
        stdDequeChildrenHelper(deque.node()->symbolGroup(),
446
                               reinterpret_cast<const ULONG32 *>(mapArray), mapSize,
447
                               deque.module(), innerType, innerTypeSize, startOffset, dequeSize, count);
448 449 450 451
    delete [] mapArray;
    return rc;
}

Friedemann Kleint's avatar
Friedemann Kleint committed
452 453 454
/* Helper class for red-black trees (std::map<>,std::set<> based on std::__Tree:
 * or Qt 5 maps).
 * We locally rebuild the structure in using instances of below class 'RedBlackTreeNode'
455 456 457 458
 * with 'left' and 'right' pointers and the values. Reason being that while it is
 * possible to write the iteration in terms of class SymbolGroupValue, it involves
 * going back up the tree over the flat node->parent pointers. Doing that in the debugger
 * sometimes ends up in nirvana, apparently due to it not being able to properly expand it.
Friedemann Kleint's avatar
Friedemann Kleint committed
459 460 461 462 463 464
 * RedBlackTreeNode has a buildMapRecursion() to build a hierarchy from a STL __Tree or
 * Qt 5 map header value, taking a helper providing node creation and left/right symbol names.
 * Use begin() to return the first node and next() to iterate. The latter are modeled
 * after the _Tree::iterator base classes. (_Tree::begin, _Tree::iterator::operator++()
 * STL tree nodes have a "value" member which is the pair of map data.
 * In Qt 5, the node is a QMapNodeBase which needs to be casted to a QMapNode<K, V>. */
465

Friedemann Kleint's avatar
Friedemann Kleint committed
466
class RedBlackTreeNode
467 468
{
private:
Friedemann Kleint's avatar
Friedemann Kleint committed
469 470
    RedBlackTreeNode(const RedBlackTreeNode &);
    RedBlackTreeNode &operator=(const RedBlackTreeNode &);
471 472

public:
Friedemann Kleint's avatar
Friedemann Kleint committed
473 474 475 476
    explicit RedBlackTreeNode(RedBlackTreeNode *p, const SymbolGroupValue &nodeValue);
    ~RedBlackTreeNode() { delete m_left; delete m_right; }

    const SymbolGroupValue &nodeValue() const { return m_node; }
477 478

    // Iterator helpers: Return first and move to next
Friedemann Kleint's avatar
Friedemann Kleint committed
479 480
    const RedBlackTreeNode *begin() const { return RedBlackTreeNode::leftMost(this); }
    static const RedBlackTreeNode *next(const RedBlackTreeNode *s);
481

Friedemann Kleint's avatar
Friedemann Kleint committed
482 483 484
    // Debug helpers
    template <class DebugFunction>
    void debug(std::ostream &os, DebugFunction df, unsigned depth = 0) const;
485

Friedemann Kleint's avatar
Friedemann Kleint committed
486 487 488
    static RedBlackTreeNode *buildMapRecursion(const SymbolGroupValue &n, ULONG64 headAddress,
                                               RedBlackTreeNode *parent,
                                               const char *leftSymbol, const char *rightSymbol);
489

Friedemann Kleint's avatar
Friedemann Kleint committed
490
    static const RedBlackTreeNode *leftMost(const RedBlackTreeNode *n);
491 492

private:
Friedemann Kleint's avatar
Friedemann Kleint committed
493 494 495
    RedBlackTreeNode *const m_parent;
    RedBlackTreeNode *m_left;
    RedBlackTreeNode *m_right;
496 497 498
    const SymbolGroupValue m_node;
};

Friedemann Kleint's avatar
Friedemann Kleint committed
499 500
RedBlackTreeNode::RedBlackTreeNode(RedBlackTreeNode *p, const SymbolGroupValue &node)
    : m_parent(p), m_left(0), m_right(0), m_node(node)
501 502 503
{
}

Friedemann Kleint's avatar
Friedemann Kleint committed
504
const RedBlackTreeNode *RedBlackTreeNode::leftMost(const RedBlackTreeNode *n)
505 506 507 508 509
{
    for ( ; n->m_left ; n = n->m_left ) ;
    return n;
}

Friedemann Kleint's avatar
Friedemann Kleint committed
510
const RedBlackTreeNode *RedBlackTreeNode::next(const RedBlackTreeNode *s)
511 512
{
    if (s->m_right) // If we have a right node, return its left-most
Friedemann Kleint's avatar
Friedemann Kleint committed
513
        return RedBlackTreeNode::leftMost(s->m_right);
514
    do { // Climb looking for 'right' subtree, that is, we are left of it
Friedemann Kleint's avatar
Friedemann Kleint committed
515
        RedBlackTreeNode *parent = s->m_parent;
516 517 518 519 520 521 522
        if (!parent || parent->m_right != s)
            return parent;
        s = parent;
    } while (true);
    return 0;
}

Friedemann Kleint's avatar
Friedemann Kleint committed
523 524 525 526 527
/* Build the tree using the helper which is asked to create the node
 * and provide the names of the "left" and "right" nodes. */
RedBlackTreeNode *RedBlackTreeNode::buildMapRecursion(const SymbolGroupValue &n, ULONG64 headAddress,
                                                      RedBlackTreeNode *parent,
                                                      const char *leftSymbol, const char *rightSymbol)
528
{
Friedemann Kleint's avatar
Friedemann Kleint committed
529 530 531
    RedBlackTreeNode *node = new RedBlackTreeNode(parent, n);
    // Get left and right nodes. A node pointing to 0 (Qt) or 'head' (STL) terminates the recursion
    if (const SymbolGroupValue left = n[leftSymbol])
532
        if (const ULONG64 leftAddr = left.pointerValue())
Friedemann Kleint's avatar
Friedemann Kleint committed
533 534 535
            if (leftAddr && leftAddr != headAddress)
                node->m_left = buildMapRecursion(left, headAddress, node, leftSymbol, rightSymbol);
    if (const SymbolGroupValue right = n[rightSymbol])
536
        if (const ULONG64 rightAddr = right.pointerValue())
Friedemann Kleint's avatar
Friedemann Kleint committed
537 538
            if (rightAddr && rightAddr != headAddress)
                node->m_right = buildMapRecursion(right, headAddress, node, leftSymbol, rightSymbol);
539 540 541
    return node;
}

Friedemann Kleint's avatar
Friedemann Kleint committed
542 543
template <class DebugFunction>
void RedBlackTreeNode::debug(std::ostream &os, DebugFunction df, unsigned depth) const
544
{
Friedemann Kleint's avatar
Friedemann Kleint committed
545 546 547 548 549
    df(m_node, os, 2 * depth);
    if (m_left)
        m_left->debug(os, df, depth + 1);
    if (m_right)
        m_right->debug(os, df, depth + 1);
550 551 552 553
}

static inline void indentStream(std::ostream &os, unsigned indent)
{
Friedemann Kleint's avatar
Friedemann Kleint committed
554
    for (unsigned i = 0; i < indent; ++i)
555 556 557 558 559
        os << ' ';
}

// Debugging helper for a SymbolGroupValue containing a __Tree::node of
// a map (assuming a std::pair inside).
Friedemann Kleint's avatar
Friedemann Kleint committed
560
static void debugMSVC2010MapNode(const SymbolGroupValue &n, std::ostream &os, unsigned indent = 0)
561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581
{
    indentStream(os, indent);
    os << "Node at " << std::hex << std::showbase << n.address()
       << std::dec << std::noshowbase
       << " Value='" << wStringToString(n.value()) << "', Parent=" << wStringToString(n["_Parent"].value())
       << ", Left=" << wStringToString(n["_Left"].value())
       << ", Right=" << wStringToString(n["_Right"].value())
       << ", nil='" <<  wStringToString(n["_Isnil"].value());
    if (const SymbolGroupValue pairBase = n["_Myval"][unsigned(0)]) {
        os << "', key='"  << wStringToString(pairBase["first"].value())
           << "', value='"   << wStringToString(pairBase["second"].value())
           << '\'';
    } else {
        os << "', key='"  << wStringToString(n["_Myval"].value()) << '\'';
    }
    os << '\n';
}

// Helper for std::map<>,std::set<> based on std::__Tree:
// Return the list of children (pair for maps, direct children for set)
static inline SymbolGroupValueVector
582
    stdTreeChildList(const SymbolGroupValue &treeIn, int count)
583
{
584 585
    if (!count)
        return SymbolGroupValueVector();
586
    // MSVC2012: many base classes.
587 588
    // MSVC2010: "class _Tree : public _Tree_val: public _Tree_nod".
    // MSVC2008: Direct class
589 590 591 592
    const SymbolGroupValue sizeV = SymbolGroupValue::findMember(treeIn, "_Mysize");
    const SymbolGroupValue tree = sizeV.parent();
    const int size = sizeV.intValue();
    if (!tree|| size <= 0)
593 594
        return SymbolGroupValueVector();
    // Build the tree and iterate it.
Friedemann Kleint's avatar
Friedemann Kleint committed
595 596 597 598 599
    // Goto root of tree (see _Tree::_Root())
    RedBlackTreeNode *nodeTree = 0;
    if (const SymbolGroupValue head = tree["_Myhead"])
        if (const ULONG64 headAddress = head.pointerValue())
            nodeTree = RedBlackTreeNode::buildMapRecursion(head["_Parent"], headAddress, 0, "_Left", "_Right");
600 601
    if (!nodeTree)
        return SymbolGroupValueVector();
Friedemann Kleint's avatar
Friedemann Kleint committed
602 603
    if (SymbolGroupValue::verbose > 1)
        nodeTree->debug(DebugPrint(), debugMSVC2010MapNode);
604 605 606
    SymbolGroupValueVector rc;
    rc.reserve(count);
    int i = 0;
Friedemann Kleint's avatar
Friedemann Kleint committed
607 608 609 610 611 612 613 614
    for (const RedBlackTreeNode *n = nodeTree->begin() ; n && i < count; n = RedBlackTreeNode::next(n), i++) {
        const SymbolGroupValue value = n->nodeValue()["_Myval"];
        if (!value) {
            delete nodeTree;
            return SymbolGroupValueVector();
        }
        rc.push_back(value);
    }
615 616 617 618 619 620 621 622
    delete nodeTree;
    if (rc.size() != count)
        return SymbolGroupValueVector();
    return rc;
}

// std::set<>: Children directly contained in list
static inline AbstractSymbolGroupNodePtrVector
623
    stdSetChildList(const SymbolGroupValue &set, unsigned count)
624
{
625
    const SymbolGroupValueVector children = stdTreeChildList(set, count);
626 627 628 629
    if (int(children.size()) != count)
        return AbstractSymbolGroupNodePtrVector();
    AbstractSymbolGroupNodePtrVector rc;
    rc.reserve(count);
630
    for (unsigned i = 0; i < count; i++)
631 632 633 634 635 636
        rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, children.at(i).node()));
    return rc;
}

// std::map<K,V>: A list of std::pair<K,V> (derived from std::pair_base<K,V>)
static inline AbstractSymbolGroupNodePtrVector
637
    stdMapChildList(const SymbolGroupValue &map, unsigned count)
638
{
639
    const SymbolGroupValueVector children = stdTreeChildList(map[unsigned(0)], count);
640
    if (children.size() != count)
641 642 643
        return AbstractSymbolGroupNodePtrVector();
    AbstractSymbolGroupNodePtrVector rc;
    rc.reserve(count);
644
    const std::string firstName = "first";
645
    for (unsigned i = 0; i < count; i++) {
646 647 648
        // MSVC2010 (only) has a std::pair_base class.
        const SymbolGroupValue key = SymbolGroupValue::findMember(children.at(i), firstName);
        const SymbolGroupValue pairBase = key.parent();
649 650 651 652 653 654 655 656 657 658 659 660
        const SymbolGroupValue value = pairBase["second"];
        if (key && value) {
            rc.push_back(MapNodeSymbolGroupNode::create(i, pairBase.address(),
                                                        pairBase.type(),
                                                        key.node(), value.node()));
        } else {
            return AbstractSymbolGroupNodePtrVector();
        }
    }
    return rc;
}

661
// QVector<T>
662
static inline AbstractSymbolGroupNodePtrVector
663
    qVectorChildList(SymbolGroupNode *n, unsigned count, const SymbolGroupValueContext &ctx)
664
{
665 666 667 668 669 670
    if (!count)
        return AbstractSymbolGroupNodePtrVector();
    const SymbolGroupValue vec(n, ctx);
    const int qtVersion = QtInfo::get(vec.context()).version;
    if (qtVersion < 5) {
        // Qt 4: QVector<T>: p/array is declared as array of T. Dereference first
671
        // element to obtain address.
672 673
        if (const SymbolGroupValue firstElementV = vec["p"]["array"][unsigned(0)]) {
            if (const ULONG64 arrayAddress = firstElementV.address()) {
674
                const std::string fixedInnerType = fixInnerType(firstElementV.type(), vec);
675
                return arrayChildList(n->symbolGroup(), arrayAddress, n->module(), fixedInnerType, count);
676 677
            }
        }
678 679 680 681 682 683 684 685 686 687 688 689 690 691
        return AbstractSymbolGroupNodePtrVector();
    }
    // Qt 5: Data are located in a pool behind 'd' (similar to QString,
    // QByteArray).
    const SymbolGroupValue dV = vec["d"][unsigned(0)];
    const SymbolGroupValue offsetV = dV["offset"];
    if (!dV || !offsetV)
        return AbstractSymbolGroupNodePtrVector();
    const ULONG64 arrayAddress = dV.address() + offsetV.intValue();
    std::vector<std::string> innerTypes = SymbolGroupValue::innerTypesOf(vec.type());
    if (arrayAddress && !innerTypes.empty()) {
        return arrayChildList(n->symbolGroup(), arrayAddress, n->module(),
                              fixInnerType(innerTypes.front(), vec),
                              count);
692
    }
693
    return AbstractSymbolGroupNodePtrVector();
694 695
}

696 697 698 699 700 701 702 703 704 705 706 707 708 709
// Helper function for arrayChildList() for use with QLists of large types that are an
// array of pointers to allocated elements: Generate a pointer sequence by reading out the array.
template <class AddressType>
class AddressArraySequence
{
public:
    explicit inline AddressArraySequence(const AddressType *array) : m_array(array) {}
    inline ULONG64 operator()() { return *m_array++; }

private:
    const AddressType *m_array;
};

// QList<>.
710
static inline AbstractSymbolGroupNodePtrVector
711
    qListChildList(const SymbolGroupValue &v, unsigned count)
712 713 714
{
    // QList<T>: d/array is declared as array of void *[]. Dereference first
    // element to obtain address.
715
    if (!count)
716
        return AbstractSymbolGroupNodePtrVector();
717 718
    const SymbolGroupValue dV = v["d"];
    if (!dV)
719
        return AbstractSymbolGroupNodePtrVector();
720 721
    const int begin = dV["begin"].intValue();
    if (begin < 0)
722
        return AbstractSymbolGroupNodePtrVector();
723 724
    const SymbolGroupValue firstElementV = dV["array"][unsigned(0)];
    if (!firstElementV)
725
        return AbstractSymbolGroupNodePtrVector();
726
     ULONG64 arrayAddress = firstElementV.address();
727
     if (!arrayAddress)
728
         return AbstractSymbolGroupNodePtrVector();
729 730
     const std::vector<std::string> innerTypes = v.innerTypes();
     if (innerTypes.size() != 1)
731
         return AbstractSymbolGroupNodePtrVector();
732
     const std::string innerType = fixInnerType(innerTypes.front(), v);
733
     const unsigned innerTypeSize = SymbolGroupValue::sizeOf(innerType.c_str());
734
     if (SymbolGroupValue::verbose)
735
         DebugPrint() << "QList " << v.name() << " inner type " << innerType << ' ' << innerTypeSize;
736
     if (!innerTypeSize)
737
         return AbstractSymbolGroupNodePtrVector();
738 739 740 741 742 743 744 745 746
     /* QList<> is:
      * 1) An array of 'void *[]' where T values are coerced into the elements for
      *    POD/pointer types and small, movable or primitive Qt types. That is, smaller
      *    elements are also aligned at 'void *' boundaries.
      * 2) An array of 'T *[]' (pointer to allocated instances) for anything else
      *    (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)
      *    isStatic depends on QTypeInfo specializations and hardcoded flags for types. */
     const unsigned pointerSize = SymbolGroupValue::pointerSize();
     arrayAddress += begin * pointerSize;
747 748
     if (SymbolGroupValue::isPointerType(innerType)) // Quick check: Any pointer is T[]
         return arrayChildList(v.node()->symbolGroup(),
749
                               AddressSequence(arrayAddress, pointerSize),
750
                               v.module(), innerType, count);
751
     // Check condition for large||static.
752
     bool isLargeOrStatic = innerTypeSize > pointerSize;
753
     if (!isLargeOrStatic && !SymbolGroupValue::isPointerType(innerType)) {
754
         const KnownType kt = knownType(innerType, false); // inner type, no 'class ' prefix.
755 756
         if (kt != KT_Unknown && !(kt & (KT_POD_Type|KT_Qt_PrimitiveType|KT_Qt_MovableType))
                 && !(kt == KT_QStringList && QtInfo::get(v.context()).version >= 5)) {
757
             isLargeOrStatic = true;
758
         }
759
     }
760
     if (SymbolGroupValue::verbose)
761
         DebugPrint() << "isLargeOrStatic " << isLargeOrStatic;
762 763
     if (isLargeOrStatic) {
         // Retrieve the pointer array ourselves to avoid having to evaluate '*(class foo**)'
764 765 766
         if (void *data = readPointerArray(arrayAddress, count, v.context()))  {
             // Generate sequence of addresses from pointer array
             const AbstractSymbolGroupNodePtrVector rc = pointerSize == 8 ?
767 768 769 770 771
                         arrayChildList(v.node()->symbolGroup(),
                                        AddressArraySequence<ULONG64>(reinterpret_cast<const ULONG64 *>(data)),
                                        v.module(), innerType, count) :
                         arrayChildList(v.node()->symbolGroup(), AddressArraySequence<ULONG32>(reinterpret_cast<const ULONG32 *>(data)),
                                        v.module(), innerType, count);
772
             delete [] data;
773
             return rc;
774
         }
775
         return AbstractSymbolGroupNodePtrVector();
776
     }
777
     return arrayChildList(v.node()->symbolGroup(),
778
                           AddressSequence(arrayAddress, pointerSize),
779
                           v.module(), innerType, count);
780 781
}

782 783 784
// Return the list of buckets of a 'QHash<>' as 'QHashData::Node *' values from
// the list of addresses passed in
template<class AddressType>
785
SymbolGroupValueVector hashBuckets(SymbolGroup *sg, const std::string &hashNodeType,
786 787 788
                                   const AddressType *pointerArray,
                                   int numBuckets,
                                   AddressType ePtr,
789
                                   const std::string &module,
790 791 792 793 794 795 796 797 798 799
                                   const SymbolGroupValueContext &ctx)
{
    SymbolGroupValueVector rc;
    rc.reserve(numBuckets);
    const AddressType *end = pointerArray + numBuckets;
    std::string errorMessage;
    // Skip 'e' special values as they are used as placeholder for reserve(d)
    // empty array elements.
    for (const AddressType *p = pointerArray; p < end; p++) {
        if (*p != ePtr) {
800
            const std::string name = SymbolGroupValue::pointedToSymbolName(*p, hashNodeType);
801
            if (SymbolGroupNode *child = sg->addSymbol(module, name, std::string(), &errorMessage)) {
802 803 804 805 806 807 808 809 810 811
                rc.push_back(SymbolGroupValue(child, ctx));
            } else {
                return std::vector<SymbolGroupValue>();
                break;
            }
        }
    }
    return rc;
}

812
// Return the node type of a QHash/QMap:
813
// "class QHash<K,V>[ *]" -> [struct] "QtCored4!QHashNode<K,V>";
814 815
static inline std::string qHashNodeType(const SymbolGroupValue &v,
                                        const char *nodeType)
816
{
817
    std::string qHashType = SymbolGroupValue::stripPointerType(v.type());
818 819
    const std::string::size_type pos = qHashType.find('<');
    if (pos != std::string::npos)
820 821 822 823 824
        qHashType.insert(pos, nodeType);
    // A map node must be qualified with the current module and
    // the Qt namespace (particularly QMapNode, QHashNodes work also for
    // the unqualified case).
    const QtInfo &qtInfo = QtInfo::get(v.context());
825
    const std::string currentModule = v.module();
826
    return QtInfo::prependModuleAndNameSpace(qHashType, currentModule, qtInfo.nameSpace);
827 828 829 830 831 832 833 834 835 836 837
}

// Return up to count nodes of type "QHashNode<K,V>" of a "class QHash<K,V>".
SymbolGroupValueVector qHashNodes(const SymbolGroupValue &v,
                                  VectorIndexType count)
{
    if (!count)
        return SymbolGroupValueVector();
    const SymbolGroupValue hashData = v["d"];
    // 'e' is used as a special value to indicate empty hash buckets in the array.
    const ULONG64 ePtr = v["e"].pointerValue();
838
    if (SymbolGroupValue::verbose)
839
        DebugPrint() << v << " Count=" << count << ",ePtr=0x" << std::hex << ePtr;
840 841 842 843 844 845 846 847 848 849 850
    if (!hashData || !ePtr)
        return SymbolGroupValueVector();
    // Retrieve the array of buckets of 'd'
    const int numBuckets = hashData["numBuckets"].intValue();
    const ULONG64 bucketArray = hashData["buckets"].pointerValue();
    if (numBuckets <= 0 || !bucketArray)
        return SymbolGroupValueVector();
    void *bucketPointers = readPointerArray(bucketArray, numBuckets, v.context());
    if (!bucketPointers)
        return SymbolGroupValueVector();
    // Get list of buckets (starting elements of 'QHashData::Node')
Friedemann Kleint's avatar
Friedemann Kleint committed
851
    const std::string dummyNodeType = QtInfo::get(v.context()).prependQtCoreModule("QHashData::Node");
852 853 854
    const SymbolGroupValueVector buckets = SymbolGroupValue::pointerSize() == 8 ?
        hashBuckets(v.node()->symbolGroup(), dummyNodeType,
                    reinterpret_cast<const ULONG64 *>(bucketPointers), numBuckets,
855
                    ePtr, v.module(), v.context()) :
856 857
        hashBuckets(v.node()->symbolGroup(), dummyNodeType,
                    reinterpret_cast<const ULONG32 *>(bucketPointers), numBuckets,
858
                    ULONG32(ePtr), v.module(), v.context());
859 860 861 862
    delete [] bucketPointers ;
    // Generate the list 'QHashData::Node *' by iterating over the linked list of
    // nodes starting at each bucket. Using the 'QHashData::Node *' instead of
    // the 'QHashNode<K,T>' is much faster. Each list has a trailing, unused
863 864
    // dummy element. The initial element as such is skipped due to the pointer/value
    // duality (since its 'next' element is identical to it when using typecast<> later on).
865 866 867 868 869 870 871 872
    SymbolGroupValueVector dummyNodeList;
    dummyNodeList.reserve(count);
    bool notEnough = true;
    const SymbolGroupValueVector::const_iterator ncend = buckets.end();
    for (SymbolGroupValueVector::const_iterator it = buckets.begin(); notEnough && it != ncend; ++it) {
        for (SymbolGroupValue l = *it; notEnough && l ; ) {
            const SymbolGroupValue next = l["next"];
            if (next && next.pointerValue()) { // Stop at trailing dummy element
873
                dummyNodeList.push_back(next);
874 875
                if (dummyNodeList.size() >= count) // Stop at maximum count
                    notEnough = false;
876
                if (SymbolGroupValue::verbose > 1)
877
                    DebugPrint() << '#' << (dummyNodeList.size() - 1) << " l=" << l << ",next=" << next;
878
                l = next;
879 880 881 882 883 884
            } else {
                break;
            }
        }
    }
    // Finally convert them into real nodes 'QHashNode<K,V> (potentially expensive)
885
    const std::string nodeType = qHashNodeType(v, "Node");
886
    if (SymbolGroupValue::verbose)
887
        DebugPrint() << "Converting into " << nodeType;
888 889 890 891
    SymbolGroupValueVector nodeList;
    nodeList.reserve(count);
    const SymbolGroupValueVector::const_iterator dcend = dummyNodeList.end();
    for (SymbolGroupValueVector::const_iterator it = dummyNodeList.begin(); it != dcend; ++it) {
892
        if (const SymbolGroupValue n = (*it).typeCast(nodeType.c_str()))
893
            nodeList.push_back(n);
Christian Stenger's avatar
Christian Stenger committed
894
        else
895 896 897 898 899 900 901
            return SymbolGroupValueVector();
    }
    return nodeList;
}

// QSet<>: Contains a 'QHash<key, QHashDummyValue>' as member 'q_hash'.
// Just dump the keys as an array.
902
static inline AbstractSymbolGroupNodePtrVector
903
    qSetChildList(const SymbolGroupValue &v, unsigned count)
904 905 906 907 908 909 910 911 912
{
    const SymbolGroupValue qHash = v["q_hash"];
    AbstractSymbolGroupNodePtrVector rc;
    if (!count || !qHash)
        return rc;
    const SymbolGroupValueVector nodes = qHashNodes(qHash, count);
    if (nodes.size() != VectorIndexType(count))
        return rc;
    rc.reserve(count);
913
    for (unsigned i = 0; i < count; i++) {
914
        if (const SymbolGroupValue key = nodes.at(i)["key"])
915
            rc.push_back(ReferenceSymbolGroupNode::createArrayNode(i, key.node()));
916
        else
917 918 919 920 921 922 923
            return AbstractSymbolGroupNodePtrVector();
    }
    return rc;
}

// QHash<>: Add with fake map nodes.
static inline AbstractSymbolGroupNodePtrVector
924
    qHashChildList(const SymbolGroupValue &v, unsigned count)
925 926 927 928
{
    AbstractSymbolGroupNodePtrVector rc;
    if (!count)
        return rc;
929 930 931 932
    const SymbolGroupValueVector nodes = qHashNodes(v, count);
    if (nodes.size() != count)
        return rc;
    rc.reserve(count);
933
    for (unsigned i = 0; i < count; i++) {
934 935 936 937 938 939 940 941
        const SymbolGroupValue &mapNode = nodes.at(i);
        const SymbolGroupValue key = mapNode["key"];
        const SymbolGroupValue value = mapNode["value"];
        if (!key || !value)
            return AbstractSymbolGroupNodePtr