scoping_analysis.cpp 14.5 KB
Newer Older
Kevin Modzelewski's avatar
Kevin Modzelewski committed
1
// Copyright (c) 2014 Dropbox, Inc.
Kevin Modzelewski's avatar
Kevin Modzelewski committed
2
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
Kevin Modzelewski's avatar
Kevin Modzelewski committed
6
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
7
//    http://www.apache.org/licenses/LICENSE-2.0
Kevin Modzelewski's avatar
Kevin Modzelewski committed
8
//
Kevin Modzelewski's avatar
Kevin Modzelewski committed
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
#include "analysis/scoping_analysis.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
16 17

#include "core/ast.h"
18
#include "core/common.h"
Kevin Modzelewski's avatar
Kevin Modzelewski committed
19 20 21 22
#include "core/util.h"

namespace pyston {

23
static bool isCompilerCreatedName(const std::string& name) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
24 25 26 27
    return name[0] == '!' || name[0] == '#';
}

class ModuleScopeInfo : public ScopeInfo {
28 29
public:
    virtual ScopeInfo* getParent() { return NULL; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
30

31
    virtual bool createsClosure() { return false; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
32

33
    virtual bool takesClosure() { return false; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
34

35 36
    bool passesThroughClosure() override { return false; }

37 38
    virtual bool refersToGlobal(const std::string& name) {
        if (isCompilerCreatedName(name))
Kevin Modzelewski's avatar
Kevin Modzelewski committed
39
            return false;
40 41 42 43 44 45

        // assert(name[0] != '#' && "should test this");
        return true;
    }
    virtual bool refersToClosure(const std::string name) { return false; }
    virtual bool saveInClosure(const std::string name) { return false; }
46 47

    virtual const std::unordered_set<std::string>& getClassDefLocalNames() { RELEASE_ASSERT(0, ""); }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
};

struct ScopingAnalysis::ScopeNameUsage {
    AST* node;
    ScopeNameUsage* parent;

    typedef std::unordered_set<std::string> StrSet;

    // Properties determined from crawling the scope:
    StrSet read;
    StrSet written;
    StrSet forced_globals;

    // Properties determined by looking at other scopes as well:
    StrSet referenced_from_nested;
    StrSet got_from_closure;
64
    StrSet passthrough_accesses; // what names a child scope accesses a name from a parent scope
Kevin Modzelewski's avatar
Kevin Modzelewski committed
65

66 67
    ScopeNameUsage(AST* node, ScopeNameUsage* parent) : node(node), parent(parent) {
        if (node->type == AST_TYPE::ClassDef) {
68 69
            AST_ClassDef* classdef = ast_cast<AST_ClassDef>(node);

70 71
            // classes have an implicit write to "__module__"
            written.insert("__module__");
72 73 74 75 76 77 78

            if (classdef->body.size() && classdef->body[0]->type == AST_TYPE::Expr) {
                AST_Expr* first_expr = ast_cast<AST_Expr>(classdef->body[0]);
                if (first_expr->value->type == AST_TYPE::Str) {
                    written.insert("__doc__");
                }
            }
79 80
        }
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
81 82 83
};

class ScopeInfoBase : public ScopeInfo {
84 85 86 87 88 89 90 91 92
private:
    ScopeInfo* parent;
    ScopingAnalysis::ScopeNameUsage* usage;

public:
    ScopeInfoBase(ScopeInfo* parent, ScopingAnalysis::ScopeNameUsage* usage) : parent(parent), usage(usage) {
        assert(parent);
        assert(usage);
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
93

94
    virtual ~ScopeInfoBase() { delete this->usage; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
95

96
    virtual ScopeInfo* getParent() { return parent; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
97

Kevin Modzelewski's avatar
Kevin Modzelewski committed
98
    virtual bool createsClosure() { return usage->referenced_from_nested.size() > 0; }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
99

100 101 102
    virtual bool takesClosure() { return usage->got_from_closure.size() > 0 || usage->passthrough_accesses.size() > 0; }

    bool passesThroughClosure() override { return usage->passthrough_accesses.size() > 0 && !createsClosure(); }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
103

104 105 106 107
    virtual bool refersToGlobal(const std::string& name) {
        // HAX
        if (isCompilerCreatedName(name))
            return false;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
108

109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
        if (usage->forced_globals.count(name))
            return true;
        return usage->written.count(name) == 0 && usage->got_from_closure.count(name) == 0;
    }
    virtual bool refersToClosure(const std::string name) {
        // HAX
        if (isCompilerCreatedName(name))
            return false;
        return usage->got_from_closure.count(name) != 0;
    }
    virtual bool saveInClosure(const std::string name) {
        // HAX
        if (isCompilerCreatedName(name))
            return false;
        return usage->referenced_from_nested.count(name) != 0;
    }
125 126 127 128 129

    virtual const std::unordered_set<std::string>& getClassDefLocalNames() {
        RELEASE_ASSERT(usage->node->type == AST_TYPE::ClassDef, "");
        return usage->written;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
130 131 132
};

class NameCollectorVisitor : public ASTVisitor {
133 134 135 136 137 138 139 140 141
private:
    AST* orig_node;
    ScopingAnalysis::NameUsageMap* map;
    ScopingAnalysis::ScopeNameUsage* cur;
    NameCollectorVisitor(AST* node, ScopingAnalysis::NameUsageMap* map) : orig_node(node), map(map) {
        assert(map);
        cur = (*map)[node];
        assert(cur);
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
142

143 144 145 146 147
public:
    void doWrite(const std::string& name) {
        cur->read.insert(name);
        cur->written.insert(name);
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
148

149
    void doRead(const std::string& name) { cur->read.insert(name); }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
150

151 152 153 154 155 156 157 158 159 160 161
    virtual bool visit_name(AST_Name* node) {
        switch (node->ctx_type) {
            case AST_TYPE::Load:
                doRead(node->id);
                break;
            case AST_TYPE::Param:
            case AST_TYPE::Store:
                doWrite(node->id);
                break;
            default:
                RELEASE_ASSERT(0, "%d", node->ctx_type);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
162
        }
163 164
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
165

166
    virtual bool visit_assert(AST_Assert* node) { return false; }
167 168 169 170 171 172 173 174 175 176 177 178
    virtual bool visit_assign(AST_Assign* node) { return false; }
    virtual bool visit_augassign(AST_AugAssign* node) { return false; }
    virtual bool visit_attribute(AST_Attribute* node) { return false; }
    virtual bool visit_binop(AST_BinOp* node) { return false; }
    virtual bool visit_boolop(AST_BoolOp* node) { return false; }
    virtual bool visit_break(AST_Break* node) { return false; }
    virtual bool visit_call(AST_Call* node) { return false; }
    virtual bool visit_compare(AST_Compare* node) { return false; }
    virtual bool visit_comprehension(AST_comprehension* node) { return false; }
    // virtual bool visit_classdef(AST_ClassDef *node) { return false; }
    virtual bool visit_continue(AST_Continue* node) { return false; }
    virtual bool visit_dict(AST_Dict* node) { return false; }
179
    virtual bool visit_dictcomp(AST_DictComp* node) { return false; }
180
    virtual bool visit_excepthandler(AST_ExceptHandler* node) { return false; }
181 182 183 184 185 186 187
    virtual bool visit_expr(AST_Expr* node) { return false; }
    virtual bool visit_for(AST_For* node) { return false; }
    // virtual bool visit_functiondef(AST_FunctionDef *node) { return false; }
    // virtual bool visit_global(AST_Global *node) { return false; }
    virtual bool visit_if(AST_If* node) { return false; }
    virtual bool visit_ifexp(AST_IfExp* node) { return false; }
    virtual bool visit_index(AST_Index* node) { return false; }
188
    virtual bool visit_keyword(AST_keyword* node) { return false; }
189 190 191 192 193 194 195
    virtual bool visit_list(AST_List* node) { return false; }
    virtual bool visit_listcomp(AST_ListComp* node) { return false; }
    // virtual bool visit_module(AST_Module *node) { return false; }
    // virtual bool visit_name(AST_Name *node) { return false; }
    virtual bool visit_num(AST_Num* node) { return false; }
    virtual bool visit_pass(AST_Pass* node) { return false; }
    virtual bool visit_print(AST_Print* node) { return false; }
196
    virtual bool visit_raise(AST_Raise* node) { return false; }
197 198 199 200 201
    virtual bool visit_repr(AST_Repr* node) { return false; }
    virtual bool visit_return(AST_Return* node) { return false; }
    virtual bool visit_slice(AST_Slice* node) { return false; }
    virtual bool visit_str(AST_Str* node) { return false; }
    virtual bool visit_subscript(AST_Subscript* node) { return false; }
202 203
    virtual bool visit_tryexcept(AST_TryExcept* node) { return false; }
    virtual bool visit_tryfinally(AST_TryFinally* node) { return false; }
204 205 206 207 208 209 210 211 212 213 214 215 216
    virtual bool visit_tuple(AST_Tuple* node) { return false; }
    virtual bool visit_unaryop(AST_UnaryOp* node) { return false; }
    virtual bool visit_while(AST_While* node) { return false; }
    virtual bool visit_with(AST_With* node) { return false; }

    virtual bool visit_branch(AST_Branch* node) { return false; }
    virtual bool visit_jump(AST_Jump* node) { return false; }


    virtual bool visit_global(AST_Global* node) {
        for (int i = 0; i < node->names.size(); i++) {
            const std::string& name = node->names[i];
            cur->forced_globals.insert(name);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
217
        }
218 219
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
220

221 222
    virtual bool visit_classdef(AST_ClassDef* node) {
        if (node == orig_node) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
223 224 225
            for (AST_stmt* s : node->body)
                s->accept(this);
            return true;
226
        } else {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
227 228 229 230 231
            for (auto* e : node->bases)
                e->accept(this);
            for (auto* e : node->decorator_list)
                e->accept(this);

232 233 234
            doWrite(node->name);
            (*map)[node] = new ScopingAnalysis::ScopeNameUsage(node, cur);
            collect(node, map);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
235 236
            return true;
        }
237
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
238

239 240
    virtual bool visit_functiondef(AST_FunctionDef* node) {
        if (node == orig_node) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
241 242 243 244 245 246 247 248 249
            for (AST_expr* e : node->args->args)
                e->accept(this);
            if (node->args->vararg.size())
                doWrite(node->args->vararg);
            if (node->args->kwarg.size())
                doWrite(node->args->kwarg);
            for (AST_stmt* s : node->body)
                s->accept(this);
            return true;
250
        } else {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
251 252 253 254 255
            for (auto* e : node->args->defaults)
                e->accept(this);
            for (auto* e : node->decorator_list)
                e->accept(this);

256 257 258 259
            doWrite(node->name);
            (*map)[node] = new ScopingAnalysis::ScopeNameUsage(node, cur);
            collect(node, map);
            return true;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
260
        }
261
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
262

263
    virtual bool visit_lambda(AST_Lambda* node) {
264 265 266 267 268 269 270 271 272 273 274 275 276 277 278
        if (node == orig_node) {
            for (AST_expr* e : node->args->args)
                e->accept(this);
            if (node->args->vararg.size())
                doWrite(node->args->vararg);
            if (node->args->kwarg.size())
                doWrite(node->args->kwarg);
            node->body->accept(this);
        } else {
            for (auto* e : node->args->defaults)
                e->accept(this);
            (*map)[node] = new ScopingAnalysis::ScopeNameUsage(node, cur);
            collect(node, map);
        }

279 280 281
        return true;
    }

282 283 284 285 286 287 288
    virtual bool visit_import(AST_Import* node) {
        for (int i = 0; i < node->names.size(); i++) {
            AST_alias* alias = node->names[i];
            if (alias->asname.size())
                doWrite(alias->asname);
            else
                doWrite(alias->name);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
289
        }
290 291
        return true;
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
292

293 294 295
    static void collect(AST* node, ScopingAnalysis::NameUsageMap* map) {
        assert(map);
        assert(map->count(node));
Kevin Modzelewski's avatar
Kevin Modzelewski committed
296

297 298 299
        NameCollectorVisitor vis(node, map);
        node->accept(&vis);
    }
Kevin Modzelewski's avatar
Kevin Modzelewski committed
300 301 302 303 304 305
};

static std::vector<ScopingAnalysis::ScopeNameUsage*> sortNameUsages(ScopingAnalysis::NameUsageMap* usages) {
    std::vector<ScopingAnalysis::ScopeNameUsage*> rtn;
    std::unordered_set<ScopingAnalysis::ScopeNameUsage*> added;

306 307
    for (const auto& p : *usages) {
        ScopingAnalysis::ScopeNameUsage* usage = p.second;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328

        std::vector<ScopingAnalysis::ScopeNameUsage*> traversed;

        while (usage && added.count(usage) == 0) {
            traversed.push_back(usage);
            usage = usage->parent;
        }

        for (int i = traversed.size() - 1; i >= 0; i--) {
            rtn.push_back(traversed[i]);
            added.insert(traversed[i]);
        }
    }

    assert(rtn.size() == usages->size());

    return rtn;
}

void ScopingAnalysis::processNameUsages(ScopingAnalysis::NameUsageMap* usages) {
    // Resolve name lookups:
329 330
    for (const auto& p : *usages) {
        ScopeNameUsage* usage = p.second;
331 332
        for (const auto& name : usage->read) {
            if (usage->forced_globals.count(name))
Kevin Modzelewski's avatar
Kevin Modzelewski committed
333
                continue;
334
            if (usage->written.count(name))
Kevin Modzelewski's avatar
Kevin Modzelewski committed
335 336
                continue;

Kevin Modzelewski's avatar
Kevin Modzelewski committed
337 338
            std::vector<ScopeNameUsage*> intermediate_parents;

339
            ScopeNameUsage* parent = usage->parent;
Kevin Modzelewski's avatar
Kevin Modzelewski committed
340 341
            while (parent) {
                if (parent->node->type == AST_TYPE::ClassDef) {
342
                    intermediate_parents.push_back(parent);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
343
                    parent = parent->parent;
344
                } else if (parent->forced_globals.count(name)) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
345
                    break;
346 347 348
                } else if (parent->written.count(name)) {
                    usage->got_from_closure.insert(name);
                    parent->referenced_from_nested.insert(name);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
349 350

                    for (ScopeNameUsage* iparent : intermediate_parents) {
351
                        iparent->passthrough_accesses.insert(name);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
352 353
                    }

Kevin Modzelewski's avatar
Kevin Modzelewski committed
354 355
                    break;
                } else {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
356
                    intermediate_parents.push_back(parent);
Kevin Modzelewski's avatar
Kevin Modzelewski committed
357 358 359 360 361 362 363 364 365 366 367
                    parent = parent->parent;
                }
            }
        }
    }


    std::vector<ScopeNameUsage*> sorted_usages = sortNameUsages(usages);

    // Construct the public-facing ScopeInfo's from the analyzed data:
    for (int i = 0; i < sorted_usages.size(); i++) {
368
        ScopeNameUsage* usage = sorted_usages[i];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
369 370
        AST* node = usage->node;

371
        ScopeInfo* parent_info = this->scopes[(usage->parent == NULL) ? this->parent_module : usage->parent->node];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
372 373 374

        switch (node->type) {
            case AST_TYPE::ClassDef:
375 376
            case AST_TYPE::FunctionDef:
            case AST_TYPE::Lambda:
Kevin Modzelewski's avatar
Kevin Modzelewski committed
377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
                this->scopes[node] = new ScopeInfoBase(parent_info, usage);
                break;
            default:
                RELEASE_ASSERT(0, "%d", usage->node->type);
                break;
        }
    }
}

ScopeInfo* ScopingAnalysis::analyzeSubtree(AST* node) {
    NameUsageMap usages;
    usages[node] = new ScopeNameUsage(node, NULL);
    NameCollectorVisitor::collect(node, &usages);

    processNameUsages(&usages);

393
    ScopeInfo* rtn = scopes[node];
Kevin Modzelewski's avatar
Kevin Modzelewski committed
394 395 396 397 398 399 400 401 402 403 404 405 406 407
    assert(rtn);
    return rtn;
}

ScopeInfo* ScopingAnalysis::getScopeInfoForNode(AST* node) {
    assert(node);

    ScopeInfo* rtn = scopes[node];
    if (rtn)
        return rtn;

    switch (node->type) {
        case AST_TYPE::ClassDef:
        case AST_TYPE::FunctionDef:
408
        case AST_TYPE::Lambda:
Kevin Modzelewski's avatar
Kevin Modzelewski committed
409 410
            return analyzeSubtree(node);
        // this is handled in the constructor:
411 412
        // case AST_TYPE::Module:
        // return new ModuleScopeInfo();
Kevin Modzelewski's avatar
Kevin Modzelewski committed
413 414 415 416 417
        default:
            RELEASE_ASSERT(0, "%d", node->type);
    }
}

418
ScopingAnalysis::ScopingAnalysis(AST_Module* m) : parent_module(m) {
Kevin Modzelewski's avatar
Kevin Modzelewski committed
419 420 421 422 423 424 425
    scopes[m] = new ModuleScopeInfo();
}

ScopingAnalysis* runScopingAnalysis(AST_Module* m) {
    return new ScopingAnalysis(m);
}
}