<commit_before>/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */

/*
 *  Main authors:
 *     <NAME> <<EMAIL>>
 */

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include <minizinc/typecheck.hh>

#include <minizinc/astiterator.hh>
#include <minizinc/astexception.hh>
#include <minizinc/hash.hh>

#include <string>
#include <sstream>

namespace MiniZinc {
  
  struct VarDeclCmp {
    UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& _pos;
    VarDeclCmp(UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& pos) : _pos(pos) {}
    bool operator()(Expression* e0, Expression* e1) {
      if (VarDecl* vd0 = Expression::dyn_cast<VarDecl>(e0)) {
        if (VarDecl* vd1 = Expression::dyn_cast<VarDecl>(e1)) {
          return _pos[vd0] < _pos[vd1];
        } else {
          return true;
        }
      } else {
        return false;
      }
    }
  };
  struct ItemCmp {
    UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& _pos;
    ItemCmp(UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& pos) : _pos(pos) {}
    bool operator()(Item* i0, Item* i1) {
      if (VarDeclI* vd0 = i0->cast<VarDeclI>()) {
        if (VarDeclI* vd1 = i1->cast<VarDeclI>()) {
          return _pos[vd0->e()] < _pos[vd1->e()];
        } else {
          return true;
        }
      } else {
        return false;
      }
    }
  };
  
  void
  TopoSorter::add(EnvI& env, VarDecl* vd, bool unique) {
    DeclMap::iterator vdi = idmap.find(vd->id());
    if (vdi == idmap.end()) {
      Decls nd; nd.push_back(vd);
      idmap.insert(vd->id(),nd);
    } else {
      if (unique) {
        GCLock lock;
        throw TypeError(env, vd->loc(),"identifier `"+vd->id()->str().str()+
                        "' already defined");
      }
      vdi->second.push_back(vd);
    }
  }
  void
  TopoSorter::remove(EnvI& env, VarDecl* vd) {
    DeclMap::iterator vdi = idmap.find(vd->id());
    assert(vdi != idmap.end());
    vdi->second.pop_back();
    if (vdi->second.empty())
      idmap.remove(vd->id());
  }

  VarDecl*
  TopoSorter::get(EnvI& env, const ASTString& id_v, const Location& loc) {
    GCLock lock;
    Id* id = new Id(Location(), id_v, NULL);
    DeclMap::iterator decl = idmap.find(id);
    if (decl==idmap.end()) {
      GCLock lock;
      throw TypeError(env,loc,"undefined identifier `"+id->str().str()+"'");
    }
    return decl->second.back();
  }

  VarDecl*
  TopoSorter::checkId(EnvI& env, Id* id, const Location& loc) {
    DeclMap::iterator decl = idmap.find(id);
    if (decl==idmap.end()) {
      GCLock lock;
      throw TypeError(env,loc,"undefined identifier `"+id->str().str()+"'");
    }
    PosMap::iterator pi = pos.find(decl->second.back());
    if (pi==pos.end()) {
      // new id
      run(env, decl->second.back());
    } else {
      // previously seen, check if circular
      if (pi->second==-1) {
        GCLock lock;
        throw TypeError(env,loc,"circular definition of `"+id->str().str()+"'");
      }
    }
    return decl->second.back();
  }

  VarDecl*
  TopoSorter::checkId(EnvI& env, const ASTString& id_v, const Location& loc) {
    GCLock lock;
    Id* id = new Id(loc,id_v,NULL);
    return checkId(env, id, loc);
  }

  void
  TopoSorter::run(EnvI& env, Expression* e) {
    if (e==NULL)
      return;
    switch (e->eid()) {
    case Expression::E_INTLIT:
    case Expression::E_FLOATLIT:
    case Expression::E_BOOLLIT:
    case Expression::E_STRINGLIT:
    case Expression::E_ANON:
      break;
    case Expression::E_SETLIT:
      {
        SetLit* sl = e->cast<SetLit>();
        if(sl->isv()==NULL)
          for (unsigned int i=0; i<sl->v().size(); i++)
            run(env,sl->v()[i]);
      }
      break;
    case Expression::E_ID:
      {
        if (e != constants().absent)
          e->cast<Id>()->decl(checkId(env, e->cast<Id>(),e->loc()));
      }
      break;
    case Expression::E_ARRAYLIT:
      {
        ArrayLit* al = e->cast<ArrayLit>();
        for (unsigned int i=0; i<al->v().size(); i++)
          run(env, al->v()[i]);
      }
      break;
    case Expression::E_ARRAYACCESS:
      {
        ArrayAccess* ae = e->cast<ArrayAccess>();
        run(env, ae->v());
        for (unsigned int i=0; i<ae->idx().size(); i++)
          run(env, ae->idx()[i]);
      }
      break;
    case Expression::E_COMP:
      {
        Comprehension* ce = e->cast<Comprehension>();
        for (int i=0; i<ce->n_generators(); i++) {
          run(env, ce->in(i));
          for (int j=0; j<ce->n_decls(i); j++) {
            add(env, ce->decl(i,j), false);
          }
        }
        if (ce->where())
          run(env, ce->where());
        run(env, ce->e());
        for (int i=0; i<ce->n_generators(); i++) {
          for (int j=0; j<ce->n_decls(i); j++) {
            remove(env, ce->decl(i,j));
          }
        }
      }
      break;
    case Expression::E_ITE:
      {
        ITE* ite = e->cast<ITE>();
        for (int i=0; i<ite->size(); i++) {
          run(env, ite->e_if(i));
          run(env, ite->e_then(i));
        }
        run(env, ite->e_else());
      }
      break;
    case Expression::E_BINOP:
      {
        BinOp* be = e->cast<BinOp>();
        run(env, be->lhs());
        run(env, be->rhs());
      }
      break;
    case Expression::E_UNOP:
      {
        UnOp* ue = e->cast<UnOp>();
        run(env, ue->e());
      }
      break;
    case Expression::E_CALL:
      {
        Call* ce = e->cast<Call>();
        for (unsigned int i=0; i<ce->args().size(); i++)
          run(env, ce->args()[i]);
      }
      break;
    case Expression::E_VARDECL:
      {
        VarDecl* ve = e->cast<VarDecl>();
        PosMap::iterator pi = pos.find(ve);
        if (pi==pos.end()) {
          pos.insert(std::pair<VarDecl*,int>(ve,-1));
          run(env, ve->ti());
          run(env, ve->e());
          ve->payload(decls.size());
          decls.push_back(ve);
          pi = pos.find(ve);
          pi->second = decls.size()-1;
        } else {
          assert(pi->second != -1);
        }<commit_msg>Recurse into binary operators using explicit stack for topological sorting (fixes stack overflow for e.g. large conjunctions)<commit_after>/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */

/*
 *  Main authors:
 *     <NAME> <<EMAIL>>
 */

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include <minizinc/typecheck.hh>

#include <minizinc/astiterator.hh>
#include <minizinc/astexception.hh>
#include <minizinc/hash.hh>

#include <string>
#include <sstream>

namespace MiniZinc {
  
  struct VarDeclCmp {
    UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& _pos;
    VarDeclCmp(UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& pos) : _pos(pos) {}
    bool operator()(Expression* e0, Expression* e1) {
      if (VarDecl* vd0 = Expression::dyn_cast<VarDecl>(e0)) {
        if (VarDecl* vd1 = Expression::dyn_cast<VarDecl>(e1)) {
          return _pos[vd0] < _pos[vd1];
        } else {
          return true;
        }
      } else {
        return false;
      }
    }
  };
  struct ItemCmp {
    UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& _pos;
    ItemCmp(UNORDERED_NAMESPACE::unordered_map<VarDecl*,int>& pos) : _pos(pos) {}
    bool operator()(Item* i0, Item* i1) {
      if (VarDeclI* vd0 = i0->cast<VarDeclI>()) {
        if (VarDeclI* vd1 = i1->cast<VarDeclI>()) {
          return _pos[vd0->e()] < _pos[vd1->e()];
        } else {
          return true;
        }
      } else {
        return false;
      }
    }
  };
  
  void
  TopoSorter::add(EnvI& env, VarDecl* vd, bool unique) {
    DeclMap::iterator vdi = idmap.find(vd->id());
    if (vdi == idmap.end()) {
      Decls nd; nd.push_back(vd);
      idmap.insert(vd->id(),nd);
    } else {
      if (unique) {
        GCLock lock;
        throw TypeError(env, vd->loc(),"identifier `"+vd->id()->str().str()+
                        "' already defined");
      }
      vdi->second.push_back(vd);
    }
  }
  void
  TopoSorter::remove(EnvI& env, VarDecl* vd) {
    DeclMap::iterator vdi = idmap.find(vd->id());
    assert(vdi != idmap.end());
    vdi->second.pop_back();
    if (vdi->second.empty())
      idmap.remove(vd->id());
  }

  VarDecl*
  TopoSorter::get(EnvI& env, const ASTString& id_v, const Location& loc) {
    GCLock lock;
    Id* id = new Id(Location(), id_v, NULL);
    DeclMap::iterator decl = idmap.find(id);
    if (decl==idmap.end()) {
      GCLock lock;
      throw TypeError(env,loc,"undefined identifier `"+id->str().str()+"'");
    }
    return decl->second.back();
  }

  VarDecl*
  TopoSorter::checkId(EnvI& env, Id* id, const Location& loc) {
    DeclMap::iterator decl = idmap.find(id);
    if (decl==idmap.end()) {
      GCLock lock;
      throw TypeError(env,loc,"undefined identifier `"+id->str().str()+"'");
    }
    PosMap::iterator pi = pos.find(decl->second.back());
    if (pi==pos.end()) {
      // new id
      run(env, decl->second.back());
    } else {
      // previously seen, check if circular
      if (pi->second==-1) {
        GCLock lock;
        throw TypeError(env,loc,"circular definition of `"+id->str().str()+"'");
      }
    }
    return decl->second.back();
  }

  VarDecl*
  TopoSorter::checkId(EnvI& env, const ASTString& id_v, const Location& loc) {
    GCLock lock;
    Id* id = new Id(loc,id_v,NULL);
    return checkId(env, id, loc);
  }

  void
  TopoSorter::run(EnvI& env, Expression* e) {
    if (e==NULL)
      return;
    switch (e->eid()) {
    case Expression::E_INTLIT:
    case Expression::E_FLOATLIT:
    case Expression::E_BOOLLIT:
    case Expression::E_STRINGLIT:
    case Expression::E_ANON:
      break;
    case Expression::E_SETLIT:
      {
        SetLit* sl = e->cast<SetLit>();
        if(sl->isv()==NULL)
          for (unsigned int i=0; i<sl->v().size(); i++)
            run(env,sl->v()[i]);
      }
      break;
    case Expression::E_ID:
      {
        if (e != constants().absent)
          e->cast<Id>()->decl(checkId(env, e->cast<Id>(),e->loc()));
      }
      break;
    case Expression::E_ARRAYLIT:
      {
        ArrayLit* al = e->cast<ArrayLit>();
        for (unsigned int i=0; i<al->v().size(); i++)
          run(env, al->v()[i]);
      }
      break;
    case Expression::E_ARRAYACCESS:
      {
        ArrayAccess* ae = e->cast<ArrayAccess>();
        run(env, ae->v());
        for (unsigned int i=0; i<ae->idx().size(); i++)
          run(env, ae->idx()[i]);
      }
      break;
    case Expression::E_COMP:
      {
        Comprehension* ce = e->cast<Comprehension>();
        for (int i=0; i<ce->n_generators(); i++) {
          run(env, ce->in(i));
          for (int j=0; j<ce->n_decls(i); j++) {
            add(env, ce->decl(i,j), false);
          }
        }
        if (ce->where())
          run(env, ce->where());
        run(env, ce->e());
        for (int i=0; i<ce->n_generators(); i++) {
          for (int j=0; j<ce->n_decls(i); j++) {
            remove(env, ce->decl(i,j));
          }
        }
      }
      break;
    case Expression::E_ITE:
      {
        ITE* ite = e->cast<ITE>();
        for (int i=0; i<ite->size(); i++) {
          run(env, ite->e_if(i));
          run(env, ite->e_then(i));
        }
        run(env, ite->e_else());
      }
      break;
    case Expression::E_BINOP:
      {
        BinOp* be = e->cast<BinOp>();
        std::vector<Expression*> todo;
        todo.push_back(be->lhs());
        todo.push_back(be->rhs());
        while (!todo.empty()) {
          Expression* e = todo.back();
          todo.pop_back();
          if (BinOp* e_bo = e->dyn_cast<BinOp>()) {
            todo.push_back(e_bo->lhs());
            todo.push_back(e_bo->rhs());
          } else {
            run(env, e);
          }
        }
      }
      break;
    case Expression::E_UNOP:
      {
        UnOp* ue = e->cast<UnOp>();
        run(env, ue->e());
      }
      break;
    case Expression::E_CALL:
      {
        Call* ce = e->cast<Call>();
        for (unsigned int i=0; i<ce->args().size(); i++)
          run(env, ce->args()[i]);
      }
      break;
    case Expression::E_VARDECL:
      {
        VarDecl* ve = e->cast<VarDecl>();
        PosMap::iterator pi = pos.find(ve);
        if (pi==pos.end()) {
          pos.insert(std::pair<VarDecl*,int>(ve,-1));
          run(env, ve->ti());
          run(env, ve->e());
          ve->payload(decls.size());
          decls.push_back(ve);
          pi = pos.find(ve);
          pi->second = decls.size()-1;
        } else {
          assert(pi->second != -1);
        }
{'fraction_non_alphanumeric': 0.1848515704550795, 'fraction_numerical': 0.005326231691078562, 'mean_word_length': 2.1525925925925926, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 202, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5958100', 'n_tokens_mistral': 4601, 'n_tokens_neox': 4565, 'n_words': 909}