symbolfinder.cpp 14.3 KB
Newer Older
hjk's avatar
hjk committed
1
/****************************************************************************
Tobias Hunger's avatar
Tobias Hunger committed
2
**
Eike Ziller's avatar
Eike Ziller committed
3 4
** Copyright (C) 2015 The Qt Company Ltd.
** Contact: http://www.qt.io/licensing
Tobias Hunger's avatar
Tobias Hunger committed
5
**
hjk's avatar
hjk committed
6
** This file is part of Qt Creator.
Tobias Hunger's avatar
Tobias Hunger committed
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.
Tobias Hunger's avatar
Tobias Hunger committed
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
Tobias Hunger's avatar
Tobias Hunger committed
27 28
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
hjk's avatar
hjk committed
29
****************************************************************************/
Tobias Hunger's avatar
Tobias Hunger committed
30

31 32 33 34 35 36
#if defined(_MSC_VER)
#pragma warning(disable:4996)
#endif

#include "symbolfinder.h"

37
#include <cplusplus/LookupContext.h>
38

39 40
#include <utils/qtcassert.h>

41 42
#include <QDebug>

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
#include <algorithm>
#include <utility>

using namespace CPlusPlus;
using namespace CppTools;

namespace {

class FindMatchingDefinition: public SymbolVisitor
{
    Symbol *_declaration;
    const OperatorNameId *_oper;
    QList<Function *> _result;

public:
    FindMatchingDefinition(Symbol *declaration)
        : _declaration(declaration)
        , _oper(0)
    {
        if (_declaration->name())
            _oper = _declaration->name()->asOperatorNameId();
    }

    QList<Function *> result() const { return _result; }

    using SymbolVisitor::visit;

    virtual bool visit(Function *fun)
    {
        if (_oper) {
            if (const Name *name = fun->unqualifiedName()) {
74
                    if (_oper->match(name))
75 76
                        _result.append(fun);
            }
77
        } else if (Function *decl = _declaration->type()->asFunctionType()) {
78
            if (fun->match(decl))
79 80 81 82 83 84 85 86 87 88 89 90 91 92
                _result.append(fun);
        }

        return false;
    }

    virtual bool visit(Block *)
    {
        return false;
    }
};

} // end of anonymous namespace

93
static const int kMaxCacheSize = 10;
94

95
SymbolFinder::SymbolFinder()
96 97 98
{}

// strict means the returned symbol has to match exactly,
99 100
// including argument count, argument types, constness and volatileness.
Function *SymbolFinder::findMatchingDefinition(Symbol *declaration,
101 102 103 104 105 106 107 108 109
                                             const Snapshot &snapshot,
                                             bool strict)
{
    if (!declaration)
        return 0;

    QString declFile = QString::fromUtf8(declaration->fileName(), declaration->fileNameLength());

    Document::Ptr thisDocument = snapshot.document(declFile);
110
    if (!thisDocument) {
111 112 113 114 115
        qWarning() << "undefined document:" << declaration->fileName();
        return 0;
    }

    Function *declarationTy = declaration->type()->asFunctionType();
116
    if (!declarationTy) {
117 118 119 120 121
        qWarning() << "not a function:" << declaration->fileName()
                   << declaration->line() << declaration->column();
        return 0;
    }

122
    foreach (const QString &fileName, fileIterationOrder(declFile, snapshot)) {
123 124
        Document::Ptr doc = snapshot.document(fileName);
        if (!doc) {
125
            clearCache(declFile, fileName);
126 127 128 129
            continue;
        }

        const Identifier *id = declaration->identifier();
130
        if (id && !doc->control()->findIdentifier(id->chars(), id->size()))
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
            continue;

        if (!id) {
            if (!declaration->name())
                continue;
            const OperatorNameId *oper = declaration->name()->asOperatorNameId();
            if (!oper)
                continue;
            if (!doc->control()->findOperatorNameId(oper->kind()))
                continue;
        }

        FindMatchingDefinition candidates(declaration);
        candidates.accept(doc->globalNamespace());

        const QList<Function *> result = candidates.result();
147
        if (!result.isEmpty()) {
148 149 150 151
            LookupContext context(doc, snapshot);

            QList<Function *> viableFunctions;

152
            LookupScope *enclosingType = context.lookupType(declaration);
153
            if (!enclosingType)
154 155 156
                continue; // nothing to do

            foreach (Function *fun, result) {
157 158 159
                if (fun->unqualifiedName()->isDestructorNameId() != declaration->unqualifiedName()->isDestructorNameId())
                    continue;

160 161 162 163 164 165 166 167 168 169 170 171
                const QList<LookupItem> declarations = context.lookup(fun->name(), fun->enclosingScope());
                if (declarations.isEmpty())
                    continue;

                const LookupItem best = declarations.first();
                if (enclosingType == context.lookupType(best.declaration()))
                    viableFunctions.append(fun);
            }

            if (viableFunctions.isEmpty())
                continue;

172
            else if (!strict && viableFunctions.length() == 1)
173 174 175 176 177
                return viableFunctions.first();

            Function *best = 0;

            foreach (Function *fun, viableFunctions) {
178
                if (!(fun->unqualifiedName()
179
                      && fun->unqualifiedName()->match(declaration->unqualifiedName()))) {
180
                    continue;
181
                }
182
                if (fun->argumentCount() == declarationTy->argumentCount()) {
183
                    if (!strict && !best)
184 185
                        best = fun;

186 187 188 189 190
                    const unsigned argc = declarationTy->argumentCount();
                    unsigned argIt = 0;
                    for (; argIt < argc; ++argIt) {
                        Symbol *arg = fun->argumentAt(argIt);
                        Symbol *otherArg = declarationTy->argumentAt(argIt);
191
                        if (!arg->type().match(otherArg->type()))
192 193 194
                            break;
                    }

195 196 197
                    if (argIt == argc
                            && fun->isConst() == declaration->type().isConst()
                            && fun->isVolatile() == declaration->type().isVolatile()) {
198
                        best = fun;
199
                    }
200 201 202
                }
            }

203
            if (strict && !best)
204 205
                continue;

206
            if (!best)
207 208 209 210 211 212 213 214
                best = viableFunctions.first();
            return best;
        }
    }

    return 0;
}

215 216
Class *SymbolFinder::findMatchingClassDeclaration(Symbol *declaration, const Snapshot &snapshot,
                                                  const LookupContext *context)
217
{
218
    if (!declaration->identifier())
219 220 221 222
        return 0;

    QString declFile = QString::fromUtf8(declaration->fileName(), declaration->fileNameLength());

223
    const bool useLocalContext = !context;
224
    foreach (const QString &file, fileIterationOrder(declFile, snapshot)) {
225 226
        Document::Ptr doc = snapshot.document(file);
        if (!doc) {
227
            clearCache(declFile, file);
228 229 230
            continue;
        }

231 232
        if (!doc->control()->findIdentifier(declaration->identifier()->chars(),
                                            declaration->identifier()->size()))
233 234
            continue;

235 236 237 238 239
        QScopedPointer<LookupContext> localContext;
        if (useLocalContext) {
            localContext.reset(new LookupContext(doc, snapshot));
            context = localContext.data();
        }
240

241
        LookupScope *type = context->lookupType(declaration);
242 243 244 245 246 247 248 249 250 251 252 253
        if (!type)
            continue;

        foreach (Symbol *s, type->symbols()) {
            if (Class *c = s->asClass())
                return c;
        }
    }

    return 0;
}

254 255 256 257 258 259 260 261
static void findDeclarationOfSymbol(Symbol *s,
                                    Function *functionType,
                                    QList<Declaration *> *typeMatch,
                                    QList<Declaration *> *argumentCountMatch,
                                    QList<Declaration *> *nameMatch)
{
    if (Declaration *decl = s->asDeclaration()) {
        if (Function *declFunTy = decl->type()->asFunctionType()) {
262
            if (functionType->match(declFunTy))
263 264 265 266 267 268 269 270 271
                typeMatch->prepend(decl);
            else if (functionType->argumentCount() == declFunTy->argumentCount())
                argumentCountMatch->prepend(decl);
            else
                nameMatch->append(decl);
        }
    }
}

272 273 274 275 276 277
void SymbolFinder::findMatchingDeclaration(const LookupContext &context,
                                           Function *functionType,
                                           QList<Declaration *> *typeMatch,
                                           QList<Declaration *> *argumentCountMatch,
                                           QList<Declaration *> *nameMatch)
{
Erik Verbruggen's avatar
Erik Verbruggen committed
278 279 280
    if (!functionType)
        return;

281
    Scope *enclosingScope = functionType->enclosingScope();
282
    while (!(enclosingScope->isNamespace() || enclosingScope->isClass()))
283
        enclosingScope = enclosingScope->enclosingScope();
284
    QTC_ASSERT(enclosingScope != 0, return);
285 286

    const Name *functionName = functionType->name();
287
    if (!functionName)
288
        return;
289

290
    LookupScope *binding = 0;
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307
    const QualifiedNameId *qName = functionName->asQualifiedNameId();
    if (qName) {
        if (qName->base())
            binding = context.lookupType(qName->base(), enclosingScope);
        else
            binding = context.globalNamespace();
        functionName = qName->name();
    }

    if (!binding) { // declaration for a global function
        binding = context.lookupType(enclosingScope);

        if (!binding)
            return;
    }

    const Identifier *funcId = functionName->identifier();
308 309 310 311 312 313 314 315 316 317
    OperatorNameId::Kind operatorNameId = OperatorNameId::InvalidOp;

    if (!funcId) {
        if (!qName)
            return;
        const OperatorNameId * const onid = qName->name()->asOperatorNameId();
        if (!onid)
            return;
        operatorNameId = onid->kind();
    }
318 319 320 321 322 323

    foreach (Symbol *s, binding->symbols()) {
        Scope *scope = s->asScope();
        if (!scope)
            continue;

324 325
        if (funcId) {
            for (Symbol *s = scope->find(funcId); s; s = s->next()) {
326
                if (!s->name() || !funcId->match(s->identifier()) || !s->type()->isFunctionType())
327 328 329 330 331 332 333 334
                    continue;
                findDeclarationOfSymbol(s, functionType, typeMatch, argumentCountMatch, nameMatch);
            }
        } else {
            for (Symbol *s = scope->find(operatorNameId); s; s = s->next()) {
                if (!s->name() || !s->type()->isFunctionType())
                    continue;
                findDeclarationOfSymbol(s, functionType, typeMatch, argumentCountMatch, nameMatch);
335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
            }
        }
    }
}

QList<Declaration *> SymbolFinder::findMatchingDeclaration(const LookupContext &context,
                                                           Function *functionType)
{
    QList<Declaration *> result;
    QList<Declaration *> nameMatch, argumentCountMatch, typeMatch;
    findMatchingDeclaration(context, functionType, &typeMatch, &argumentCountMatch, &nameMatch);
    result.append(typeMatch);
    result.append(argumentCountMatch);
    return result;
}

351
QStringList SymbolFinder::fileIterationOrder(const QString &referenceFile, const Snapshot &snapshot)
352
{
353 354
    if (m_filePriorityCache.contains(referenceFile)) {
        checkCacheConsistency(referenceFile, snapshot);
355
    } else {
356 357
        foreach (Document::Ptr doc, snapshot)
            insertCache(referenceFile, doc->fileName());
358 359
    }

360 361
    QStringList files = m_filePriorityCache.value(referenceFile).values();

362 363
    trackCacheUse(referenceFile);

364
    return files;
365 366
}

367
void SymbolFinder::checkCacheConsistency(const QString &referenceFile, const Snapshot &snapshot)
368 369 370 371
{
    // We only check for "new" files, which which are in the snapshot but not in the cache.
    // The counterpart validation for "old" files is done when one tries to access the
    // corresponding document and notices it's now null.
372
    const QSet<QString> &meta = m_fileMetaCache.value(referenceFile);
373
    foreach (const Document::Ptr &doc, snapshot) {
374 375
        if (!meta.contains(doc->fileName()))
            insertCache(referenceFile, doc->fileName());
376 377 378
    }
}

379
void SymbolFinder::clearCache(const QString &referenceFile, const QString &comparingFile)
380
{
381 382 383
    m_filePriorityCache[referenceFile].remove(computeKey(referenceFile, comparingFile),
                                              comparingFile);
    m_fileMetaCache[referenceFile].remove(comparingFile);
384 385
}

386
void SymbolFinder::insertCache(const QString &referenceFile, const QString &comparingFile)
387 388
{
    // We want an ordering such that the documents with the most common path appear first.
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
    m_filePriorityCache[referenceFile].insert(computeKey(referenceFile, comparingFile),
                                              comparingFile);
    m_fileMetaCache[referenceFile].insert(comparingFile);
}

void SymbolFinder::trackCacheUse(const QString &referenceFile)
{
    if (!m_recent.isEmpty()) {
        if (m_recent.last() == referenceFile)
            return;
        m_recent.removeOne(referenceFile);
    }

    m_recent.append(referenceFile);

    // We don't want this to grow too much.
405
    if (m_recent.size() > kMaxCacheSize) {
406
        const QString &oldest = m_recent.takeFirst();
407 408 409
        m_filePriorityCache.remove(oldest);
        m_fileMetaCache.remove(oldest);
    }
410 411 412 413 414 415 416 417 418 419 420 421
}

int SymbolFinder::computeKey(const QString &referenceFile, const QString &comparingFile)
{
    // As similar the path from the comparing file is to the path from the reference file,
    // the smaller the key is, which is then used for sorting the map.
    std::pair<QString::const_iterator,
              QString::const_iterator> r = std::mismatch(referenceFile.begin(),
                                                         referenceFile.end(),
                                                         comparingFile.begin());
    return referenceFile.length() - (r.first - referenceFile.begin());
}