1| // Synopsis C++ Parser: lookup.cc source file
    2| // Implementation of the Lookup class
    3| 
    4| // $Id: lookup.cc,v 1.10 2002/11/17 12:11:44 chalky Exp $
    5| //
    6| // This file is a part of Synopsis.
    7| // Copyright (C) 2001, 2002 Stephen Davies
    8| //
    9| // Synopsis is free software; you can redistribute it and/or modify it
   10| // under the terms of the GNU General Public License as published by
   11| // the Free Software Foundation; either version 2 of the License, or
   12| // (at your option) any later version.
   13| //
   14| // This program is distributed in the hope that it will be useful,
   15| // but WITHOUT ANY WARRANTY; without even the implied warranty of
   16| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   17| // General Public License for more details.
   18| //
   19| // You should have received a copy of the GNU General Public License
   20| // along with this program; if not, write to the Free Software
   21| // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   22| // 02111-1307, USA.
   23| 
   24| // $Log: lookup.cc,v $
   25| // Revision 1.10  2002/11/17 12:11:44  chalky
   26| // Reformatted all files with astyle --style=ansi, renamed fakegc.hh
   27| //
   28| //
   29| 
   30| #include <map>
   31| #include <typeinfo>
   32| #include <sstream>
   33| #include <algorithm>
   34| 
   35| #include "lookup.hh"
   36| #include "builder.hh"
   37| #include "type.hh"
   38| #include "dict.hh"
   39| #include "swalker.hh"
   40| #include "scopeinfo.hh"
   41| #include "typeinfo.hh"
   42| 
   43| // for debugging
   44| #include "dumper.hh"
   45| #include "strace.hh"
   46| 
   47| //. Simplify names. Typically only used for accessing vectors and iterators
   48| using namespace Types;
   49| using namespace AST;
   50| 
   51| //
   52| // Class ScopeInfo
   53| //
   54| ScopeInfo::ScopeInfo(AST::Scope* s)
   55|         : is_using(false)
   56| {
   57|     scope_decl = s;
   58|     search.push_back(this);
   59|     dict = new Dictionary();
   60|     access = AST::Default;
   61| }
   62| 
   63| // FIXME: why is there a using scope?
   64| ScopeInfo::ScopeInfo(ScopeInfo* s)
   65|         : is_using(true)
   66| {
   67|     scope_decl = s->scope_decl;
   68|     dict = s->dict;
   69| }
   70| 
   71| ScopeInfo::~ScopeInfo()
   72| {
   73|     //if (is_using == false)
   74|     //  delete dict;
   75| }
   76| 
   77| int
   78| ScopeInfo::getCount(const std::string& name)
   79| {
   80|     return ++nscounts[name];
   81| }
   82| 
   83| 
   84| /////// FIXME: wtf is this doing here??
   85| namespace
   86| {
   87| //. This class is very similar to ostream_iterator, except that it works on
   88| //. pointers to types
   89| template <typename T>
   90| class ostream_ptr_iterator
   91| {
   92|     std::ostream* out;
   93|     const char* sep;
   94| public:
   95|     ostream_ptr_iterator(std::ostream& o, const char* s) : out(&o), sep(s)
   96|     {}
   97|     ostream_ptr_iterator<T>& operator =(const T* value)
   98|     {
   99|         *out << *value;
  100|         if (sep)
  101|             *out << sep;
  102|         return *this;
  103|     }
  104|     ostream_ptr_iterator<T>& operator *()
  105|     {
  106|         return *this;
  107|     }
  108|     ostream_ptr_iterator<T>& operator ++()
  109|     {
  110|         return *this;
  111|     }
  112|     ostream_ptr_iterator<T>& operator ++(int)
  113|     {
  114|         return *this;
  115|     }
  116| };
  117| }
  118| 
  119| // defined in common.hh
  120| std::string join(const ScopedName& strs, const std::string& sep)
  121| {
  122|     ScopedName::const_iterator iter = strs.begin();
  123|     if (iter == strs.end())
  124|         return "";
  125|     std::string str = *iter++;
  126|     while (iter != strs.end())
  127|         str += sep + *iter++;
  128|     return str;
  129| }
  130| 
  131| //. Output operator for debugging
  132| std::ostream& operator << (std::ostream& o, TypeInfo& i)
  133| {
  134|     TypeFormatter tf;
  135|     o << "[" << tf.format(i.type);
  136|     if (i.is_const)
  137|         o << " (const)";
  138|     if (i.is_volatile)
  139|         o << " (volatile)";
  140|     if (i.deref)
  141|         o << " " << i.deref << "*";
  142|     o << "]";
  143|     return o;
  144| }
  145| 
  146| 
  147| //
  148| // Struct Lookup::Private
  149| //
  150| 
  151| #if 0
  152| struct Lookup::Private
  153| {
  154|     //. A map of AST::Scope's ScopeInfo objects
  155|     typedef std::map<AST::Scope*, ScopeInfo*> ScopeMap;
  156|     ScopeMap map;
  157| 
  158|     //. A map of name references
  159|     typedef std::map<ScopedName, std::vector<AST::Reference> > RefMap;
  160|     RefMap refs;
  161| };
  162| #endif
  163| 
  164| //
  165| // Class Lookup
  166| //
  167| 
  168| Lookup::Lookup(Builder* builder)
  169| {
  170|     m_builder = builder;
  171| }
  172| 
  173| Lookup::~Lookup()
  174| {
  175|     // TODO Delete all ...
  176|     //delete m;
  177| }
  178| 
  179| //. Finds or creates a cached Scope
  180| ScopeInfo* Lookup::find_info(AST::Scope* decl)
  181| {
  182|     return m_builder->find_info(decl);
  183| }
  184| 
  185| AST::Scope* Lookup::global()
  186| {
  187|     return m_builder->global();
  188| }
  189| 
  190| AST::Scope* Lookup::scope()
  191| {
  192|     return m_builder->scope();
  193| }
  194| 
  195| //
  196| // Type Methods
  197| //
  198| 
  199| //. Predicate class that is true if the object passed to the constructor is a
  200| //. type, as opposed to a modifier or a parametrized, etc
  201| class isType : public Types::Visitor
  202| {
  203|     bool m_value;
  204| public:
  205|     //. constructor. Visits the given type thereby setting the value
  206|     isType(Types::Named* type) : m_value(false)
  207|     {
  208|         type->accept(this);
  209|     }
  210|     //. bool operator, returns the value determined by visitation during
  211|     //. construction
  212|     operator bool()
  213|     {
  214|         return m_value;
  215|     }
  216|     //. Okay
  217|     void visit_base(Types::Base*)
  218|     {
  219|         m_value = true;
  220|     }
  221|     //. Okay
  222|     void visit_unknown(Types::Unknown*)
  223|     {
  224|         m_value = true;
  225|     }
  226|     //. Okay if not a function declaration
  227|     void visit_declared(Types::Declared* type)
  228|     {
  229|         // Depends on what was declared: Everything but function is okay
  230|         if (dynamic_cast<AST::Function*>(type->declaration()))
  231|             m_value = false;
  232|         else
  233|             m_value = true;
  234|     }
  235|     //. Okay if a template dependent arg
  236|     void visit_dependent(Types::Dependent*)
  237|     {
  238|         m_value = true;
  239|     }
  240|     //. Fallback: Not okay
  241|     void visit_type(Types::Type*)
  242|     {
  243|         m_value = false;
  244|     }
  245| };
  246| 
  247| // Public method to lookup a type
  248| Types::Named* Lookup::lookupType(const std::string& name, bool func_okay)
  249| {
  250|     STrace trace("Lookup::lookupType(name, func_okay)");
  251|     Types::Named* type = lookup(name, func_okay);
  252|     if (type)
  253|         return type;
  254|     // Not found, declare it unknown
  255|     //cout << "Warning: Name "<<name<<" not found in "<<m_filename<<endl;
  256|     return m_builder->create_unknown(name);
  257| }
  258| 
  259| // Private method to lookup a type in the current scope
  260| Types::Named* Lookup::lookup(const std::string& name, bool func_okay)
  261| {
  262|     STrace trace("Lookup::lookup(name, func_okay)");
  263|     const ScopeSearch& search = m_builder->scopeinfo()->search;
  264|     return lookup(name, search, func_okay);
  265| }
  266| 
  267| //. Looks up the name in the scope of the given scope
  268| Types::Named* Lookup::lookupType(const std::string& name, AST::Scope* decl)
  269| {
  270|     STrace trace("Lookup::lookupType(name,scope)");
  271|     ScopeInfo* scope = find_info(decl);
  272|     return lookup(name, scope->search);
  273| }
  274| 
  275| class FunctionHeuristic
  276| {
  277|     typedef std::vector<Types::Type*> v_Type;
  278|     typedef v_Type::iterator vi_Type;
  279|     typedef std::vector<AST::Parameter*> v_Param;
  280|     typedef v_Param::iterator vi_Param;
  281| 
  282|     v_Type m_args;
  283|     int cost;
  284| #ifdef DEBUG
  285| 
  286|     STrace trace;
  287| public:
  288|     //. Constructor - takes arguments to match functions against
  289|     FunctionHeuristic(const v_Type& v)
  290|             : m_args(v), trace("FunctionHeuristic")
  291|     {
  292|         TypeFormatter tf;
  293|         std::ostringstream buf;
  294|         for (size_t index = 0; index < v.size(); index++)
  295|         {
  296|             if (index)
  297|                 buf << ", ";
  298|             buf << tf.format(v[index]);
  299|         }
  300|         //buf << std::ends;
  301|         LOG("Function arguments: " << buf.str());
  302|     }
  303| #else
  304| public:
  305|     //. Constructor - takes arguments to match functions against
  306|     FunctionHeuristic(const v_Type& v)
  307|             : m_args(v)
  308|     { }
  309| #endif
  310| 
  311|     //. Heuristic operator, returns 'cost' of given function - higher is
  312|     //. worse, 1000 means no match
  313|     int operator ()(AST::Function* func)
  314|     {
  315|         cost = 0;
  316|         int num_args = m_args.size();
  317|         v_Param* params =& func->parameters();
  318|         bool func_ellipsis = hasEllipsis(params);
  319|         int num_params = params->size() - func_ellipsis;
  320|         int num_default = countDefault(params);
  321| 
  322|         // Check number of params first
  323|         if (!func_ellipsis && num_args > num_params)
  324|             cost = 1000;
  325|         if (num_args < num_params - num_default)
  326|             cost = 1000;
  327| 
  328|         if (cost < 1000)
  329|         {
  330|             // Now calc cost of each argument in turn
  331|             int max_arg = num_args > num_params ? num_params : num_args;
  332|             for (int index = 0; index < max_arg; index++)
  333|                 calcCost(m_args[index], (*params)[index]->type());
  334|         }
  335| 
  336| #ifdef DEBUG
  337|         LOG("Function: " << func->name() << " -- Cost is " << cost);
  338| #endif
  339| 
  340|         return cost;
  341|     }
  342| 
  343| private:
  344|     //. Find an ellipsis as the last arg
  345|     bool hasEllipsis(v_Param* params)
  346|     {
  347|         if (params->size() == 0)
  348|             return false;
  349|         Types::Type* back = params->back()->type();
  350|         if (Types::Base* base = dynamic_cast<Types::Base*>(back))
  351|             if (base->name().size() == 1 && base->name().front() == "...")
  352|                 return true;
  353|         return false;
  354|     }
  355| 
  356|     //. Returns the number of parameters with default values. Counts from the
  357|     //. back and stops when it finds one without a default.
  358|     int countDefault(v_Param* params)
  359|     {
  360|         v_Param::reverse_iterator iter = params->rbegin(), end = params->rend();
  361|         int count = 0;
  362|         while (iter != end)
  363|         {
  364|             AST::Parameter* param = *iter++;
  365|             if (!param->value().size())
  366|                 break;
  367|             count++;
  368|         }
  369|         return count;
  370|     }
  371| 
  372|     //. Calculate the cost of converting 'arg' into 'param'. The cost is
  373|     //. accumulated on the 'cost' member variable.
  374|     void calcCost(Types::Type* arg_t, Types::Type* param_t)
  375|     {
  376|         TypeFormatter tf;
  377|         if (!arg_t)
  378|             return;
  379|         TypeInfo arg(arg_t), param(param_t);
  380| #ifdef DEBUG
  381|         // std::cout << arg << param << std::endl;
  382|         // // std::cout << tf.format(type) <<","<<tf.format(param_type) << std::endl;
  383| #endif
  384|         // Null types convert to any ptr with no cost
  385|         if (arg.is_null && param.deref > 0)
  386|             return;
  387|         // Different types is bad
  388|         if (arg.type != param.type)
  389|             cost += 10;
  390|         // Different * levels is also bad
  391|         if (arg.deref != param.deref)
  392|             cost += 10;
  393|         // Worse constness is bad
  394|         if (arg.is_const > param.is_const)
  395|             cost += 5;
  396|     }
  397| };
  398| 
  399| //. Looks up the function in the given scope with the given args.
  400| AST::Function* Lookup::lookupFunc(const std::string& name, AST::Scope* decl, const std::vector<Types::Type*>& args)
  401| {
  402|     STrace trace("Lookup::lookupFunc");
  403|     TypeFormatter tf;
  404|     // Now loop over the search scopes
  405|     const ScopeSearch& search = find_info(decl)->search;
  406|     ScopeSearch::const_iterator s_iter = search.begin();
  407|     typedef std::vector<AST::Function*> v_Function;
  408|     v_Function functions;
  409| 
  410|     // Loop over precalculated search list
  411|     while (s_iter != search.end())
  412|     {
  413|         ScopeInfo* scope = *s_iter++;
  414| 
  415|         // Check if dict has it
  416|         if (scope->dict->has_key(name))
  417|         {
  418|             findFunctions(name, scope, functions);
  419|         }
  420|         // If not a dummy scope, resolve the set
  421|         if (scope->is_using == false && !functions.empty())
  422|         {
  423|             // Return best function (or throw error)
  424|             int cost;
  425|             AST::Function* func = bestFunction(functions, args, cost);
  426|             if (cost < 1000)
  427|                 return func;
  428|             throw ERROR("No appropriate function found.");
  429|         }
  430|     }
  431| 
  432|     throw ERROR("No matching functions found.");
  433| }
  434| 
  435| // Operator lookup
  436| AST::Function* Lookup::lookupOperator(const std::string& oper, Types::Type* left_type, Types::Type* right_type)
  437| {
  438|     STrace trace("Lookup::lookupOperator("+oper+",left,right)");
  439|     // Find some info about the two types
  440|     TypeInfo left(left_type), right(right_type);
  441|     bool left_user = !!dynamic_cast<Types::Declared*>(left_type) && !left.deref;
  442|     bool right_user = !!dynamic_cast<Types::Declared*>(right_type) && !right.deref;
  443| 
  444|     // First check if the types are user-def or enum
  445|     if (!left_user && !right_user)
  446|         return NULL;
  447| 
  448|     std::vector<AST::Function*> functions;
  449|     std::vector<Types::Type*> args;
  450|     AST::Function* best_method = NULL, *best_func = NULL;
  451|     int best_method_cost, best_func_cost;
  452| 
  453|     // Member methods of left_type
  454|     try
  455|     {
  456|         AST::Class* clas = Types::declared_cast<AST::Class>(left.type);
  457|         // Construct the argument list
  458|         args.push_back(right_type);
  459| 
  460|         try
  461|         {
  462|             findFunctions(oper, find_info(clas), functions);
  463| 
  464|             best_method = bestFunction(functions, args, best_method_cost);
  465|         }
  466|         catch (const Dictionary::KeyError&)
  467|         {
  468|             best_method = NULL;
  469|         }
  470| 
  471|         // Clear functions and args for use below
  472|         functions.clear();
  473|         args.clear();
  474|     }
  475|     catch (const Types::wrong_type_cast&)
  476|     { /* ignore: not a class */
  477|     }
  478| 
  479|     // Non-member functions
  480|     // Loop over the search scopes
  481|     const ScopeSearch& search = m_builder->scopeinfo()->search;
  482|     ScopeSearch::const_iterator s_iter = search.begin();
  483|     while (s_iter != search.end())
  484|     {
  485|         ScopeInfo* scope = *s_iter++;
  486|         // Check if dict has any names that match
  487|         if (!scope->dict->has_key(oper))
  488|             continue;
  489| 
  490|         // Get the matching functions from the dictionary
  491|         findFunctions(oper, scope, functions);
  492| 
  493|         // Scope rules say once you find any results: stop
  494|         break;
  495|     }
  496| 
  497|     // Koenig Rule: add operators from namespaces of arguments
  498|     // void findKoenigFunctions(oper, functions, args);
  499|     if (left_user)
  500|         try
  501|         {
  502|             ScopedName enclosing_name = Types::type_cast<Types::Named>(left.type)->name();
  503|             enclosing_name.pop_back();
  504|             if (enclosing_name.size())
  505|             {
  506|                 ScopeInfo* scope = find_info( Types::declared_cast<AST::Scope>(lookupType(enclosing_name, false, global())) );
  507|                 findFunctions(oper, scope, functions);
  508|             }
  509|         }
  510|         catch (const Types::wrong_type_cast& e)
  511|         {}
  512| 
  513|     if (right_user)
  514|         try
  515|         {
  516|             ScopedName enclosing_name = Types::type_cast<Types::Named>(right.type)->name();
  517|             enclosing_name.pop_back();
  518|             if (enclosing_name.size())
  519|             {
  520|                 ScopeInfo* scope = find_info( Types::declared_cast<AST::Scope>(lookupType(enclosing_name, false, global())) );
  521|                 findFunctions(oper, scope, functions);
  522|             }
  523|         }
  524|         catch (const Types::wrong_type_cast& e)
  525|         {}
  526| 
  527|     // Add builtin operators to aide in best-function resolution
  528|     // NYI
  529| 
  530|     // Puts left and right types into args
  531|     args.push_back(left_type);
  532|     args.push_back(right_type);
  533|     // Find best non-method function
  534|     best_func = bestFunction(functions, args, best_func_cost);
  535| 
  536|     // Return best method or function
  537|     if (best_method)
  538|     {
  539|         if (best_func)
  540|         {
  541|             if (best_func_cost < best_method_cost)
  542|                 return best_func;
  543|             else
  544|                 return best_method;
  545|         }
  546|         else
  547|         {
  548|             return best_method;
  549|         }
  550|     }
  551|     else
  552|     {
  553|         if (best_func)
  554|             return best_func;
  555|         else
  556|             return NULL;
  557|     }
  558| }
  559| 
  560| void Lookup::findFunctions(const std::string& name, ScopeInfo* scope, AST::Function::vector& functions)
  561| {
  562|     STrace trace("Lookup::findFunctions");
  563| 
  564|     // Get the matching names from the dictionary
  565|     try
  566|     {
  567|         Named::vector types = scope->dict->lookupMultiple(name);
  568| 
  569|         // Put only the AST::Functions into 'functions'
  570|         for (Named::vector::iterator iter = types.begin(); iter != types.end();)
  571|             try
  572|             {
  573|                 functions.push_back( Types::declared_cast<AST::Function>(*iter++) );
  574|             }
  575|             catch (const Types::wrong_type_cast& )
  576|             {
  577|                 throw ERROR("looked up func '"<<name<<"'wasnt a func!");
  578|             }
  579|     }
  580|     catch (Dictionary::KeyError)
  581|     { }
  582| }
  583| 
  584| AST::Function* Lookup::bestFunction(const AST::Function::vector& functions, const Types::Type::vector& args, int& cost)
  585| {
  586|     // Quick sanity check
  587|     if (!functions.size())
  588|         return NULL;
  589|     // Find best function using a heuristic
  590|     FunctionHeuristic heuristic(args);
  591|     Function::vector::const_iterator iter = functions.begin(), end = functions.end();
  592|     AST::Function* best_func = *iter++;
  593|     int best = heuristic(best_func);
  594|     while (iter != end)
  595|     {
  596|         AST::Function* func = *iter++;
  597|         int cost = heuristic(func);
  598|         if (cost < best)
  599|         {
  600|             best = cost;
  601|             best_func = func;
  602|         }
  603|     }
  604|     cost = best;
  605|     return best_func;
  606| }
  607| 
  608| // Private method to lookup a type in the specified search space
  609| Types::Named* Lookup::lookup(const std::string& name, const ScopeSearch& search, bool func_okay) throw ()
  610| {
  611|     STrace trace("Lookup::lookup(name,search,func_okay)");
  612|     ScopeSearch::const_iterator s_iter = search.begin();
  613|     Named::vector results;
  614|     while (s_iter != search.end())
  615|     {
  616|         ScopeInfo* scope = *s_iter++;
  617| 
  618|         // Check if dict has it
  619|         if (scope->dict->has_key(name))
  620|         {
  621|             if (results.empty())
  622|                 results = scope->dict->lookupMultiple(name);
  623|             else
  624|             {
  625|                 Named::vector temp_result = scope->dict->lookupMultiple(name);
  626|                 std::copy(temp_result.begin(), temp_result.end(),
  627|                           std::back_inserter(results));
  628|             }
  629|         }
  630|         // If not a dummy scope, resolve the set
  631|         if (scope->is_using == false && !results.empty())
  632|         {
  633| #ifdef DEBUG
  634|             Named::vector save_results = results;
  635| #endif
  636|             // Remove the unknowns
  637|             Types::Unknown* unknown = NULL;
  638|             Named::vector::iterator r_iter = results.begin();
  639|             while (r_iter != results.end())
  640|                 if ((unknown = dynamic_cast<Types::Unknown*>(*r_iter)) != NULL)
  641|                     r_iter = results.erase(r_iter);
  642|                 else if (!func_okay && !isType(*r_iter))
  643|                     r_iter = results.erase(r_iter);
  644|                 else
  645|                     ++r_iter;
  646|             // Should be either 1 non-unknowns left or nothing but with
  647|             // 'unknown' set
  648|             if (results.size() == 0 && unknown != NULL)
  649|                 return unknown;
  650|             if (results.size() == 0)
  651|                 // This means there was only functions in the list, which we are
  652|                 // ignoring
  653|                 continue;
  654|             if (results.size() == 1)
  655|                 // Exactly one match! return it
  656|                 return results[0];
  657|             // Store in class var?
  658|             LOG("Multiple candidates!");
  659| #ifdef DEBUG
  660| 
  661|             for (r_iter = save_results.begin(); r_iter != save_results.end(); ++r_iter)
  662|                 LOG(" - '" << (*r_iter)->name() << "' - " << typeid(**r_iter).name());
  663| #endif
  664| 
  665|             return results[0];
  666|         }
  667|     }
  668|     return NULL;
  669| }
  670| 
  671| class InheritanceAdder
  672| {
  673|     std::list<AST::Class*>& open_list;
  674| public:
  675|     InheritanceAdder(std::list<AST::Class*>& l) : open_list(l)
  676|     {}
  677|     InheritanceAdder(const InheritanceAdder& i) : open_list(i.open_list)
  678|     {}
  679|     void operator() (AST::Inheritance* i)
  680|     {
  681|         try
  682|         {
  683|             AST::Class* parent = Types::declared_cast<AST::Class>(i->parent());
  684|             open_list.push_back(parent);
  685|         }
  686|         catch (const Types::wrong_type_cast&)
  687|         {
  688|             // ?? ignore for now
  689|         }
  690|     }
  691| };
  692| 
  693| //. Private Qualified type lookup
  694| Types::Named* Lookup::lookupQual(const std::string& name, const ScopeInfo* scope, bool func_okay)
  695| {
  696|     STrace trace("Lookup::lookupQual");
  697|     //LOG("name: " << name << " in: " << scope->scope_decl->name());
  698|     // First determine: class or namespace
  699|     if (AST::Class* the_class = dynamic_cast<AST::Class*>(scope->scope_decl))
  700|     {
  701|         // A class: search recursively, in order, through base classes
  702|         // FIXME: read up about overriding, hiding, virtual bases and funcs,
  703|         // etc
  704|         std::list<AST::Class*> open_list;
  705|         open_list.push_back(the_class);
  706|         while (!open_list.empty())
  707|         {
  708|             AST::Class* clas = open_list.front();
  709|             open_list.pop_front();
  710|             ScopeInfo* scope = find_info(clas);
  711|             if (scope->dict->has_key(name))
  712|             {
  713|                 try
  714|                 {
  715|                     Types::Named* named = scope->dict->lookup(name);
  716|                     if (func_okay || isType(named))
  717|                     {
  718|                         return named;
  719|                     }
  720|                     // Else it's a function and a type was wanted: keep looking
  721|                 }
  722|                 catch (const Dictionary::MultipleError& e)
  723|                 {
  724|                     // FIXME: check for duplicates etc etc
  725|                 }
  726|                 catch (const Dictionary::KeyError& e)
  727|                 {
  728|                     std::cerr << "Warning: Key error when has_key said yes" << std::endl;
  729|                 }
  730|             }
  731|             // Add base classes to open list
  732|             std::for_each(clas->parents().begin(), clas->parents().end(),
  733|                           InheritanceAdder(open_list));
  734|         }
  735|     }
  736|     else if (dynamic_cast<AST::Namespace*>(scope->scope_decl))
  737|     {
  738|         // A namespace: search recursively through using declarations
  739|         // constructing a conflict set - dont traverse using declarations of
  740|         // any namespace which has an entry for 'name'. Each NS only once
  741|         std::list<const ScopeInfo*> open, closed;
  742|         open.push_back(scope);
  743|         std::vector<Types::Named*> results;
  744|         while (!open.empty())
  745|         {
  746|             const ScopeInfo* ns = open.front();
  747|             open.pop_front();
  748|             // Check if 'ns' is on closed list
  749|             if (std::find(closed.begin(), closed.end(), ns) != closed.end())
  750|                 continue;
  751|             // Add to closed list
  752|             closed.push_back(ns);
  753|             // Check if 'ns' has 'name'
  754|             if (ns->dict->has_key(name))
  755|             {
  756|                 // Add all results to results list
  757|                 if (results.empty())
  758|                     results = ns->dict->lookupMultiple(name);
  759|                 else
  760|                 {
  761|                     std::vector<Types::Named*> temp = ns->dict->lookupMultiple(name);
  762|                     std::copy(temp.begin(), temp.end(),
  763|                               back_inserter(results));
  764|                 }
  765|             }
  766|             else
  767|             {
  768|                 // Add 'using' Scopes to open list
  769|                 std::copy(ns->using_scopes.begin(), ns->using_scopes.end(),
  770|                           back_inserter(open));
  771|             }
  772|         }
  773|         // Now we have a set of results
  774|         if (!results.size())
  775|         {
  776|             LOG("No results! Looking up '" << name << "'");
  777|             return NULL;
  778|         }
  779|         // FIXME: figure out what to do about multiple
  780|         Types::Named* best = NULL;
  781|         int best_score = -1;
  782|         for (std::vector<Types::Named*>::iterator iter = results.begin();
  783|                 iter != results.end(); iter++)
  784|         {
  785|             // Fixme.. create a Score visitor
  786|             int score = 0;
  787|             Types::Named* type = *iter;
  788|             if (Types::Declared* declared = dynamic_cast<Types::Declared*>(type))
  789|             {
  790|                 score++;
  791|                 if (AST::Declaration* decl = declared->declaration())
  792|                 {
  793|                     score++;
  794|                     if (dynamic_cast<AST::Forward*>(decl))
  795|                         score--;
  796|                 }
  797|             }
  798|             if (score > best_score)
  799|             {
  800|                 best_score = score;
  801|                 best = type;
  802|             }
  803|         }
  804| 
  805|         return best;
  806|     }
  807|     // Not class or NS - which is illegal for a qualified (but coulda been
  808|     // template etc?:)
  809|     LOG("Not class or namespace: " << typeid(scope->scope_decl).name());
  810|     return NULL;
  811| }
  812| 
  813| //. Public Qualified Type Lookup
  814| Types::Named* Lookup::lookupType(const std::vector<std::string>& names, bool func_okay, AST::Scope* start_scope)
  815| {
  816|     STrace trace("Lookup::lookupType(vector names,search,func_okay)");
  817|     //LOG("looking up '" << names << "' in " << (start_scope?start_scope->name() : m_scope->name()));
  818|     Types::Named* type = NULL;
  819|     ScopeInfo* scope = NULL;
  820|     std::vector<std::string>::const_iterator n_iter = names.begin();
  821|     // Setup the initial scope
  822|     std::string name = *n_iter;
  823|     if (!name.size())
  824|     {
  825|         // Qualified name starts with :: so always start at global scope
  826|         type = global()->declared();
  827|     }
  828|     else
  829|     {
  830|         // Lookup first name as usual
  831|         if (start_scope)
  832|             type = lookupType(name, start_scope);
  833|         else
  834|             type = lookupType(name);
  835|     }
  836|     ++n_iter;
  837| 
  838|     // Look over every identifier in the qualified name
  839|     while (n_iter != names.end())
  840|     {
  841|         name = *n_iter++;
  842|         try
  843|         {
  844|             // FIXME: this should use some sort of visitor
  845|             AST::Declaration* decl = Types::declared_cast<AST::Declaration>(type);
  846|             if (AST::Typedef* tdef = dynamic_cast<AST::Typedef*>(decl))
  847|             {
  848|                 type = Types::type_cast<Types::Named>(tdef->alias());
  849|             }
  850|             // Find cached scope from 'type'
  851|             scope = find_info( Types::declared_cast<AST::Scope>(type) );
  852|         }
  853|         catch (const Types::wrong_type_cast& )
  854|         {
  855|             // Abort lookup
  856|             throw ERROR("qualified lookup found a type (" << type->name() << ") that wasn't a scope finding: " << names);
  857|         }
  858|         // Find the named type in the current scope
  859|         type = lookupQual(name, scope, func_okay && n_iter == names.end());
  860|         if (!type)
  861|             // Abort lookup
  862|             break;
  863|     }
  864| 
  865|     if (!type)
  866|     {
  867|         LOG("Not found -> creating Unknown");
  868|         // Not found! Add Type.Unknown of scoped name
  869|         std::string name = names[0];
  870|         for (n_iter = names.begin(); ++n_iter != names.end();)
  871|             name += "::" + *n_iter;
  872|         return m_builder->create_unknown(name);
  873|     }
  874|     return type;
  875| }
  876| 
  877| //. Maps a scoped name into a vector of scopes and the final type. Returns
  878| //. true on success.
  879| bool Lookup::mapName(const ScopedName& names, std::vector<AST::Scope*>& o_scopes, Types::Named*& o_type)
  880| {
  881|     STrace trace("Lookup::mapName");
  882|     AST::Scope* ast_scope = global();
  883|     ScopedName::const_iterator iter = names.begin();
  884|     ScopedName::const_iterator last = names.end();
  885|     last--;
  886|     ScopedName scoped_name;
  887| 
  888|     // Start scope name at global level
  889|     scoped_name.push_back("");
  890| 
  891|     // Sanity check
  892|     if (iter == names.end())
  893|         return false;
  894| 
  895|     // Loop through all containing scopes
  896|     while (iter != last)
  897|     {
  898|         //const std::string& name = *iter++;
  899|         scoped_name.push_back(*iter++);
  900|         Types::Named* type = lookupType(scoped_name);
  901|         if (!type)
  902|         {
  903|             LOG("Warning: failed to lookup " << scoped_name << " in global scope");
  904|             return false;
  905|         }
  906|         try
  907|         {
  908|             ast_scope = Types::declared_cast<AST::Scope>(type);
  909|         }
  910|         catch (const Types::wrong_type_cast&)
  911|         {
  912|             LOG("Warning: looked up scope wasnt a scope!" << scoped_name);
  913|             return false;
  914|         }
  915|         o_scopes.push_back(ast_scope);
  916|     }
  917| 
  918|     // iter now == last, which can be any type
  919|     scoped_name.push_back(*iter);
  920|     Types::Named* type = lookupType(scoped_name, true);
  921|     if (!type)
  922|     {
  923|         //find_info(ast_scope)->dict->dump();
  924|         LOG("\nWarning: final type lookup wasn't found!" << *iter);
  925|         return false;
  926|     }
  927| 
  928|     o_type = type;
  929|     return true;
  930| }
  931| 
  932| Types::Type* Lookup::arrayOperator(Types::Type* object, Types::Type* arg, AST::Function*& func_oper)
  933| {
  934|     STrace trace("Lookup::arrayOperator");
  935|     func_oper = NULL;
  936|     // First decide if should use derefence or methods
  937|     TypeInfo info(object);
  938|     if (info.deref)
  939|     {
  940|         // object is of pointer type, so just deref it
  941|         // Check for typedef
  942|         try
  943|         {
  944|             object = Types::declared_cast<AST::Typedef>(object)->alias();
  945|         }
  946|         catch (const Types::wrong_type_cast&)
  947|         { /* ignore -- not a typedef */
  948|         }
  949|         // Check for modifier
  950|         if (Types::Modifier* mod = dynamic_cast<Types::Modifier*>(object))
  951|         {
  952|             typedef Types::Type::Mods Mods;
  953|             Types::Modifier* newmod = new Types::Modifier(mod->alias(), mod->pre(), mod->post());
  954|             for (Mods::iterator iter = newmod->post().begin(); iter != newmod->post().end(); iter++)
  955|             {
  956|                 if (*iter == "*" || *iter == "[]")
  957|                 {
  958|                     newmod->post().erase(iter);
  959|                     return newmod;
  960|                 }
  961|             }
  962|             //delete newmod;
  963|             throw ERROR("Unable to dereference type for array operator!");
  964|         }
  965|         throw ERROR("Unknown type for array operator!");
  966|     }
  967| 
  968|     // Hmm object type -- try for [] method
  969|     AST::Class* clas;
  970|     try
  971|     {
  972|         clas = Types::declared_cast<AST::Class>(info.type);
  973|     }
  974|     catch (const Types::wrong_type_cast&)
  975|     {
  976|         TypeFormatter tf;
  977|         throw ERROR("Not deref and not class type for array operator! " << tf.format(info.type) << " <-- " << tf.format(object));
  978|     }
  979| 
  980|     Function::vector functions;
  981|     try
  982|     {
  983|         findFunctions("[]", find_info(clas), functions);
  984|     }
  985|     catch (const Dictionary::KeyError&)
  986|     {
  987|         throw ERROR("No array operator for class " << clas->name());
  988|     }
  989| 
  990|     // Make args list
  991|     std::vector<Types::Type*> args;
  992|     args.push_back(arg);
  993| 
  994|     // Find best function
  995|     int cost;
  996|     AST::Function* func = bestFunction(functions, args, cost);
  997|     if (!func || cost >= 1000)
  998|         throw ERROR("No best function found for array operator.");
  999|     func_oper = func;
 1000|     return func->return_type();
 1001| }
 1002| 
 1003| Types::Named* Lookup::resolveType(Types::Named* type)
 1004| {
 1005|     STrace trace("Lookup::resolveType(named)");
 1006|     try
 1007|     {
 1008|         ScopedName& name = type->name();
 1009|         LOG("Resolving '" << name << "'");
 1010| 
 1011|         ScopedName::iterator iter = name.begin(), end = name.end() - 1;
 1012|         AST::Scope* scope = global();
 1013|         while (iter != end)
 1014|         {
 1015|             // Find *iter in scope
 1016|             Types::Named* scope_type = find_info(scope)->dict->lookup(*iter++);
 1017|             scope = Types::declared_cast<AST::Scope>(scope_type);
 1018|         }
 1019|         LOG("Looking up '"<<(*iter)<<"' in '"<< ((scope==global())?"global":scope->name().back()) << "'");
 1020|         // Scope is now the containing scope of the type we are checking
 1021|         return find_info(scope)->dict->lookup(*iter);
 1022|     }
 1023|     catch (const Types::wrong_type_cast& )
 1024|     {
 1025|         LOG("resolveType failed! bad cast.");
 1026|     }
 1027|     catch (Dictionary::KeyError e)
 1028|     {
 1029|         LOG("resolveType failed! key error: '"<<e.name<<"'");
 1030|     }
 1031|     catch (Dictionary::MultipleError e)
 1032|     {
 1033|         LOG("resolveType failed! multiple:" << e.types.size());
 1034|         std::vector<Types::Named*>::iterator iter = e.types.begin();
 1035|         while (iter != e.types.end())
 1036|         {
 1037|             LOG(" +" << (*iter)->name());
 1038|             iter++;
 1039|         }
 1040|     }
 1041|     catch (...)
 1042|     {
 1043|         // There shouldn't be any errors, but just in case...
 1044|         throw ERROR("resolveType failed with unknown error!");
 1045|     }
 1046|     return type;
 1047| }
 1048| 
 1049| std::string Lookup::dumpSearch(ScopeInfo* scope)
 1050| {
 1051|     ScopeSearch& search = scope->search;
 1052|     std::ostringstream buf;
 1053|     buf << "Search for ";
 1054|     if (scope->scope_decl->name().size() == 0)
 1055|         buf << "global";
 1056|     else
 1057|         buf << this->scope()->name();
 1058|     buf << " is now: ";
 1059|     ScopeSearch::iterator iter = search.begin();
 1060|     while (iter != search.end())
 1061|     {
 1062|         buf << (iter==search.begin() ? "" : ", ");
 1063|         const ScopedName& name = (*iter)->scope_decl->name();
 1064|         if (name.size())
 1065|             if ( (*iter)->is_using )
 1066|                 buf << "(" << name << ")";
 1067|             else
 1068|                 buf << name;
 1069|         else
 1070|             buf << "global";
 1071|         ++iter;
 1072|     }
 1073|     //buf << std::ends;
 1074|     return buf.str();
 1075| }
 1076| 
 1077| 
 1078| // vim: set ts=8 sts=4 sw=4 et: