Synopsis - Cross-Reference

  1//
  2// Copyright (C) 2002 Stephen Davies
  3// Copyright (C) 2002 Stefan Seefeld
  4// All rights reserved.
  5// Licensed to the public under the terms of the GNU LGPL (>= 2),
  6// see the file COPYING for details.
  7//
  8
  9#include <map>
 10#include <typeinfo>
 11#include <sstream>
 12#include <algorithm>
 13
 14#include "Builder.hh"
 15#include "Types.hh"
 16#include "Dictionary.hh"
 17#include "Walker.hh"
 18#include "ScopeInfo.hh"
 19#include "Lookup.hh"
 20#include "TypeInfo.hh"
 21#include "STrace.hh"
 22
 23//. Simplify names. Typically only used for accessing vectors and iterators
 24using namespace Types;
 25using namespace ASG;
 26
 27//. Utility method
 28ScopedName extend(const ScopedName& name, const std::string& str)
 29{
 30    ScopedName ret = name;
 31    ret.push_back(str);
 32    return ret;
 33}
 34
 35
 36/////// FIXME: wtf is this doing here??
 37namespace
 38{
 39//. This class is very similar to ostream_iterator, except that it works on
 40//. pointers to types
 41template <typename T>
 42class ostream_ptr_iterator
 43{
 44    std::ostream* out;
 45    const char* sep;
 46public:
 47    ostream_ptr_iterator(std::ostream& o, const char* s) : out(&o), sep(s)
 48    {}
 49    ostream_ptr_iterator<T>& operator =(const T* value)
 50    {
 51        *out << *value;
 52        if (sep)
 53            *out << sep;
 54        return *this;
 55    }
 56    ostream_ptr_iterator<T>& operator *()
 57    {
 58        return *this;
 59    }
 60    ostream_ptr_iterator<T>& operator ++()
 61    {
 62        return *this;
 63    }
 64    ostream_ptr_iterator<T>& operator ++(int)
 65    {
 66        return *this;
 67    }
 68};
 69}
 70
 71//. Formats a vector<string> to the output, joining the strings with ::'s.
 72//. This operator is prototyped in builder.hh and can be used from other
 73//. modules
 74std::ostream& operator <<(std::ostream& out, const ScopedName& vec)
 75{
 76    return out << join(vec, "::");
 77}
 78
 79//
 80// Struct Builder::Private
 81//
 82
 83struct Builder::Private
 84{
 85    typedef std::map<ASG::Scope*, ScopeInfo*> ScopeMap;
 86    ScopeMap map;
 87
 88    //. A map of name references
 89    typedef std::map<ScopedName, std::vector<ASG::Reference> > RefMap;
 90    RefMap refs;
 91
 92    //. A list of builtin declarations
 93    Declaration::vector builtin_decls;
 94};
 95
 96//
 97// Class Builder
 98//
 99
100Builder::Builder(ASG::SourceFile* file)
101{
102  // m_file was originally initialized to 0. Why ??
103    m_file = file;
104    m_unique = 1;
105    m = new Private;
106    ScopedName name;
107    m_scope = m_global = new ASG::Namespace(file, 0, "global", name);
108    ScopeInfo* global = find_info(m_global);
109    m_scopes.push_back(global);
110    // Insert the global base types
111    Types::Base* t_bool, *t_null;
112    ASG::Declaration* decl;
113    global->dict->insert(create_base("char"));
114    global->dict->insert(t_bool = create_base("bool"));
115    global->dict->insert(create_base("short"));
116    global->dict->insert(create_base("int"));
117    global->dict->insert(create_base("long"));
118    global->dict->insert(create_base("unsigned"));
119    global->dict->insert(create_base("unsigned long"));
120    global->dict->insert(create_base("float"));
121    global->dict->insert(create_base("double"));
122    global->dict->insert(create_base("void"));
123    global->dict->insert(create_base("..."));
124    global->dict->insert(create_base("long long"));
125    global->dict->insert(create_base("long double"));
126    global->dict->insert(t_null = create_base("__null_t"));
127    // Add a variables for true
128    name.clear();
129    name.push_back("true");
130    decl = new ASG::Const(file, -1, "const", name, t_bool, "true");
131    global->dict->insert(decl);
132    m->builtin_decls.push_back(decl);
133    // Add a variable for false
134    name.clear();
135    name.push_back("false");
136    decl = new ASG::Const(file, -1, "const", name, t_bool, "false");
137    global->dict->insert(decl);
138    m->builtin_decls.push_back(decl);
139    // Add a variable for null pointer types (g++ #defines NULL to __null)
140    name.clear();
141    name.push_back("__null");
142    decl = new ASG::Variable(file, -1, "variable", name, t_null, false);
143    global->dict->insert(decl);
144    m->builtin_decls.push_back(decl);
145
146    // Create the Lookup helper
147    m_lookup = new Lookup(this);
148}
149
150Builder::~Builder()
151{
152    // TODO Delete all ...
153    delete m_lookup;
154    delete m;
155}
156
157//. Finds or creates a cached Scope
158ScopeInfo* Builder::find_info(ASG::Scope* decl)
159{
160    Private::ScopeMap::iterator iter = m->map.find(decl);
161    if (iter == m->map.end())
162    {
163        ScopeInfo* scope = new ScopeInfo(decl);
164        m->map.insert(Private::ScopeMap::value_type(decl, scope));
165        return scope;
166    }
167    return iter->second;
168}
169
170void Builder::set_access(ASG::Access axs)
171{
172    m_scopes.back()->access = axs;
173}
174
175void Builder::set_file(ASG::SourceFile* file)
176{
177    m_file = file;
178}
179
180const Declaration::vector& Builder::builtin_decls() const
181{
182    return m->builtin_decls;
183}
184
185//
186// ASG Methods
187//
188
189void Builder::add(ASG::Declaration* decl, bool is_template)
190{
191    ScopeInfo* scopeinfo;
192    ASG::Declaration::vector* decls;
193    if (is_template)
194    {
195        scopeinfo = m_scopes[m_scopes.size()-2];
196        decls = &scopeinfo->scope_decl->declarations();
197    }
198    else
199    {
200        scopeinfo = m_scopes.back();
201        decls = &m_scope->declarations();
202    }
203    // Set access
204    decl->set_access(scopeinfo->access);
205    // Add to name dictionary
206    scopeinfo->dict->insert(decl);
207
208    const std::string& scope_type = scopeinfo->scope_decl->type();
209    if (scope_type != "local" && scope_type != "function")
210      decls->push_back(decl);
211    decl->file()->declarations().push_back(decl);
212}
213
214void Builder::add(Types::Named* type)
215{
216    // Add to name dictionary
217    m_scopes.back()->dict->insert(type);
218}
219
220void Builder::add_macros(const std::vector<ASG::Macro*>& macros)
221{
222    std::vector<ASG::Macro*>::const_iterator iter;
223    for (iter = macros.begin(); iter != macros.end(); iter++)
224	m_global->declarations().push_back(*iter);
225
226}
227
228ASG::Namespace* Builder::start_namespace(const std::string& n, NamespaceType nstype)
229{
230    std::string name = n, type_str;
231    ASG::Namespace* ns = 0;
232    bool generated = false;
233    // Decide what to do based on the given namespace type
234    switch (nstype)
235    {
236    case NamespaceNamed:
237      type_str = "namespace";
238      { // Check if namespace already exists
239        Dictionary* dict = scopeinfo()->dict;
240        if (dict->has_key(name))
241          try
242          {
243            Types::Named::vector types = dict->lookupMultiple(name);
244            ns = Types::declared_cast<ASG::Namespace>(*types.begin());
245          }
246          catch (const Types::wrong_type_cast&) {}
247        }
248        break;
249    case NamespaceAnon:
250        type_str = "module";
251        { // name is the filename. Wrap it in {}'s. only keep after last /
252            size_t slash_at = name.rfind('/');
253            if (slash_at != std::string::npos)
254                name.erase(0, slash_at + 1);
255            name = "{" + name + "}";
256        }
257        break;
258    case NamespaceUnique:
259        type_str = "local";
260        { // name is empty or the type. Encode it with a unique number
261            if (!name.size())
262                name = "ns";
263            int count = m_scopes.back()->getCount(name);
264            std::ostringstream buf;
265            buf << '`' << name;
266            if (count > 1)
267                buf << count;
268            name = buf.str();
269        }
270        break;
271    case NamespaceTemplate:
272        type_str = "template";
273        { // name is empty or the type. Encode it with a unique number
274            if (!name.size())
275                name = "template";
276            int count = m_scopes.back()->getCount(name);
277            std::ostringstream buf;
278            buf << '`' << name << count;
279            name = buf.str();
280        }
281        break;
282    }
283    // Create a new namespace object unless we already found one
284    if (ns == 0)
285    {
286        generated = true;
287        // Create the namspace
288        if (nstype == NamespaceTemplate)
289            ns = new ASG::Namespace(m_file, 0, type_str, m_scope->name());
290        else
291        {
292            // Generate a nested name
293            ScopedName ns_name = extend(m_scope->name(), name);
294            ns = new ASG::Namespace(m_file, 0, type_str, ns_name);
295            add(ns);
296        }
297    }
298    // Create ScopeInfo object. Search is this NS plus enclosing NS's search
299    ScopeInfo* ns_info = find_info(ns);
300    ScopeInfo* current = m_scopes.back();
301    // For anon namespaces, we insert the anon ns into the parent search
302    if (nstype == NamespaceAnon && generated)
303        current->search.push_back(ns_info);
304    // Initialize search to same as parent scope if we generated a new NS
305    if (generated)
306        std::copy(current->search.begin(), current->search.end(),
307                  std::back_inserter(ns_info->search));
308
309    // Push stack
310    m_scopes.push_back(ns_info);
311    m_scope = ns;
312    return ns;
313}
314
315void Builder::end_namespace()
316{
317    // TODO: Check if it is a namespace...
318    m_scopes.pop_back();
319    m_scope = m_scopes.back()->scope_decl;
320}
321
322// Utility class to recursively add base classes to given search
323void Builder::add_class_bases(ASG::Class* clas, ScopeSearch& search)
324{
325    ASG::Inheritance::vector::iterator inh_iter = clas->parents().begin();
326    while (inh_iter != clas->parents().end())
327    {
328        ASG::Inheritance* inh = *inh_iter++;
329        Types::Type* type = inh->parent();
330        try
331        {
332            ASG::Class* base = Types::declared_cast<ASG::Class>(type);
333            // Found a base class, so look it up
334            ScopeInfo* scope = find_info(base);
335            search.push_back(scope);
336            // Recursively add..
337            add_class_bases(base, search);
338        }
339        catch (const Types::wrong_type_cast&)
340        { /* TODO: handle typedefs and parameterized types */
341        }
342    }
343}
344
345void Builder::update_class_base_search()
346{
347    ScopeInfo* scope = m_scopes.back();
348    ASG::Class* clas = dynamic_cast<ASG::Class*>(scope->scope_decl);
349    if (!clas)
350        return;
351    ScopeSearch search = scope->search;
352    ScopeSearch::iterator iter = search.begin();
353    scope->search.clear();
354    // Add the scope itself
355    scope->search.push_back(*iter++);
356    // Add base classes
357    add_class_bases(clas, scope->search);
358    // Add containing scopes, stored in search
359    while (iter != search.end())
360        scope->search.push_back(*iter++);
361}
362
363ASG::Class* Builder::start_class(int lineno, const std::string& type, const std::string& name,
364                                 ASG::Parameter::vector* templ_params, std::string const &primary_name)
365{
366    // Generate the name
367    ASG::Class* class_ = 0;
368    bool is_template = templ_params && templ_params->size();
369    bool is_specialization = *name.rbegin() == '>';
370    if (is_template)
371    {
372      ScopedName class_name = extend(m_scopes[m_scopes.size()-2]->scope_decl->name(), name);
373      ASG::ClassTemplate *ct = new ASG::ClassTemplate(m_file, lineno, type, class_name, is_specialization);
374      Types::Template* templ = new Types::Template(class_name, ct, *templ_params);
375      ct->set_template_id(templ);
376      add(ct, true);
377      class_ = ct;
378    }
379    else
380    {
381      ScopedName class_name = extend(m_scope->name(), name);
382      class_ = new ASG::Class(m_file, lineno, type, class_name, is_specialization);
383      add(class_);
384    }
385    // Push stack. Search is this Class plus base Classes plus enclosing NS's search
386    ScopeInfo* class_info = find_info(class_);
387    class_info->access = (type == "struct" ? ASG::Public : ASG::Private);
388    std::copy(scopeinfo()->search.begin(), scopeinfo()->search.end(),
389              std::back_inserter(class_info->search));
390    m_scopes.push_back(class_info);
391    m_scope = class_;
392
393    return class_;
394}
395
396// Declaration of a previously forward declared class (ie: must find and
397// replace previous forward declaration in the appropriate place)
398ASG::Class* Builder::start_class(int lineno, const std::string& type, const ScopedName& names)
399{
400    // Find the forward declaration of this class
401    Types::Named* named = m_lookup->lookupType(names);
402    // Must be either unknown or declared->forward
403    Types::Unknown* unknown = dynamic_cast<Types::Unknown*>(named);
404    if (!unknown)
405    {
406        Types::Declared* declared = dynamic_cast<Types::Declared*>(named);
407        if (!declared)
408        {
409            std::cerr << "Fatal: Qualified class name did not reference a declared type." << std::endl;
410            exit(1);
411        }
412        ASG::Forward* forward = dynamic_cast<ASG::Forward*>(declared->declaration());
413        if (!forward)
414        {
415            std::cerr << "Fatal: Qualified class name did not reference a forward declaration." << std::endl;
416            exit(1);
417        }
418    }
419    // Create the Class
420    ASG::Class* ns = new ASG::Class(m_file, lineno, type, named->name(), false);
421    // Add to container scope
422    ScopedName scope_name = names;
423    scope_name.pop_back();
424    Types::Declared* scope_type = dynamic_cast<Types::Declared*>(m_lookup->lookupType(scope_name));
425    if (!scope_type)
426    {
427        std::cerr << "Fatal: Qualified class name was not in a declaration." << std::endl;
428        exit(1);
429    }
430    ASG::Scope* scope = dynamic_cast<ASG::Scope*>(scope_type->declaration());
431    if (!scope)
432    {
433        std::cerr << "Fatal: Qualified class name was not in a scope." << std::endl;
434        exit(1);
435    }
436    // Set access
437    //decl->setAccess(m_scopes.back()->access);
438    // Add declaration
439    scope->declarations().push_back(ns);
440    // Add to name dictionary
441    ScopeInfo* scope_info = find_info(scope);
442    scope_info->dict->insert(ns);
443    // Push stack. Search is this Class plus enclosing scopes. bases added later
444    ScopeInfo* ns_info = find_info(ns);
445    ns_info->access = (type == "struct" ? ASG::Public : ASG::Private);
446    std::copy(scope_info->search.begin(), scope_info->search.end(),
447              std::back_inserter(ns_info->search));
448    m_scopes.push_back(ns_info);
449    m_scope = ns;
450    return ns;
451}
452
453void Builder::end_class()
454{
455    // Check if it is a class...
456    m_scopes.pop_back();
457    m_scope = m_scopes.back()->scope_decl;
458}
459
460ASG::Namespace* Builder::start_template()
461{
462    return start_namespace("", NamespaceTemplate);
463}
464
465void Builder::end_template()
466{
467    end_namespace();
468}
469
470
471//. Start function impl scope
472void Builder::start_function_impl(const ScopedName& name)
473{
474    STrace trace("Builder::start_function_impl");
475    // Create the Namespace
476    ASG::Namespace* ns = new ASG::Namespace(m_file, 0, "function", name);
477    ScopeInfo* ns_info = find_info(ns);
478    // if this is a function template, add the template parameter scope for
479    // dependent types.
480    if (m_scopes.back()->scope_decl->type() == "template")
481      ns_info->search.push_back(m_scopes.back());
482    ScopeInfo* scope_info;
483    if (name.size() > 1)
484    {
485        // Find container scope
486        std::vector<std::string> scope_name = name;
487        scope_name.pop_back();
488        scope_name.insert(scope_name.begin(), ""); // force lookup from global, not current scope, since name is fully qualified
489        Types::Declared* scope_type = dynamic_cast<Types::Declared*>(m_lookup->lookupType(scope_name));
490        if (!scope_type)
491        {
492            throw ERROR("Warning: Qualified func name was not in a declaration. Parent scope is:" << scope_name);
493        }
494        ASG::Scope* scope = dynamic_cast<ASG::Scope*>(scope_type->declaration());
495        if (!scope)
496        {
497            throw ERROR("Warning: Qualified func name was not in a scope.");
498        }
499        scope_info = find_info(scope);
500    }
501    else
502    {
503        scope_info = find_info(m_global);
504    }
505    // Add to name dictionary TODO: this is for debugging only!
506    scope_info->dict->insert(ns);
507    // Push stack. Search is this Class plus enclosing scopes. bases added later
508    std::copy(scope_info->search.begin(), scope_info->search.end(),
509              std::back_inserter(ns_info->search));
510
511    m_scopes.push_back(ns_info);
512    m_scope = ns;
513}
514
515//. End function impl scope
516void Builder::end_function_impl()
517{
518    m_scopes.pop_back();
519    m_scope = m_scopes.back()->scope_decl;
520}
521
522//. Add an function
523ASG::Function* Builder::add_function(int line, const std::string& name,
524                                     const std::vector<std::string>& premod,
525				     Types::Type* ret,
526                                     const std::vector<std::string>& postmod,
527                                     const std::string& realname,
528				     ASG::Parameter::vector* templ_params)
529{
530    // Find the parent scope, depending on whether this is a template or not
531    ASG::Scope* parent_scope;
532    if (templ_params)
533        parent_scope = m_scopes[m_scopes.size()-2]->scope_decl;
534    else
535        parent_scope = m_scope;
536
537    // Determine the new scoped name
538    ScopedName func_name = extend(parent_scope->name(), name);
539
540    // Decide whether this is a member function (aka operation) or just a
541    // function
542    ASG::Function* func;
543    if (dynamic_cast<ASG::Class*>(parent_scope))
544    {
545      char const *type = (templ_params && templ_params->size()) ? "member function template" : "member function";
546      func = new ASG::Operation(m_file, line, type, func_name, premod, ret, postmod, realname);
547    }
548    else
549    {
550      char const *type = (templ_params && templ_params->size()) ? "function template" : "function";
551      func = new ASG::Function(m_file, line, type, func_name, premod, ret, postmod, realname);
552    }
553    // Create template type
554    if (templ_params)
555    {
556        Types::Template* templ = new Types::Template(func_name, func, *templ_params);
557        func->set_template_id(templ);
558        add(func, true);
559    }
560    else
561        add(func);
562    return func;
563}
564
565//. Add a variable
566ASG::Variable* Builder::add_variable(int line, const std::string& name, Types::Type* vtype, bool constr, const std::string& type)
567{
568    // Generate the name
569    ScopedName scope = m_scope->name();
570    scope.push_back(name);
571    ASG::Variable* var = new ASG::Variable(m_file, line, type, scope, vtype, constr);
572    add(var);
573    return var;
574}
575
576ASG::Const* Builder::add_constant(int line, const std::string& name, Types::Type* cType, const std::string& type, std::string const &value)
577{
578    // Generate the name
579    ScopedName scope = m_scope->name();
580    scope.push_back(name);
581    ASG::Const* c = new ASG::Const(m_file, line, type, scope, cType, value);
582    add(c);
583    return c;
584}
585
586void Builder::add_this_variable()
587{
588    // First find out if we are in a method
589    ASG::Scope* func_ns = m_scope;
590    ScopedName name = func_ns->name();
591    name.pop_back();
592    name.insert(name.begin(), std::string());
593    Types::Named* clas_named = m_lookup->lookupType(name, false);
594    ASG::Class* clas;
595    try
596    {
597        clas = Types::declared_cast<ASG::Class>(clas_named);
598    }
599    catch (const Types::wrong_type_cast& )
600        // Not in a method -- so dont add a 'this'
601    {
602        return;
603    }
604
605    // clas is now the ASG::Class of the enclosing class
606    Types::Type::Mods pre, post;
607    post.push_back("*");
608    Types::Modifier* t_this = new Types::Modifier(clas->declared(), pre, post);
609    add_variable(-1, "this", t_this, false, "this");
610}
611
612//. Add a typedef
613ASG::Typedef* Builder::add_typedef(int line, const std::string& name, Types::Type* alias, bool constr)
614{
615    // Generate the name
616    ScopedName scoped_name = extend(m_scope->name(), name);
617    // Create the object
618    ASG::Typedef* tdef = new ASG::Typedef(m_file, line, "typedef", scoped_name, alias, constr);
619    add(tdef);
620    return tdef;
621}
622
623//. Add an enumerator
624ASG::Enumerator* Builder::add_enumerator(int line, const std::string& name, const std::string& value)
625{
626    ScopedName scoped_name = extend(m_scope->name(), name);
627    ASG::Enumerator* enumor = new ASG::Enumerator(m_file, line, "enumerator", scoped_name, value);
628    add(enumor->declared());
629    return enumor;
630}
631
632//. Add an enum
633ASG::Enum* Builder::add_enum(int line, const std::string& name, const std::vector<ASG::Enumerator*>& enumors)
634{
635    ScopedName scoped_name = extend(m_scope->name(), name);
636    ASG::Enum* theEnum = new ASG::Enum(m_file, line, "enum", scoped_name);
637    theEnum->enumerators() = enumors;
638    add(theEnum);
639    return theEnum;
640}
641
642//. Add tail comment
643ASG::Builtin *Builder::add_tail_comment(int line)
644{
645    ScopedName name;
646    name.push_back("EOS");
647    ASG::Builtin *builtin = new ASG::Builtin(m_file, line, "EOS", name);
648    add(builtin);
649    return builtin;
650}
651
652// A functor that adds only inheritances which are class objects to a given
653// list
654class InheritanceAdder
655{
656    std::list<ASG::Class*>& open_list;
657public:
658    InheritanceAdder(std::list<ASG::Class*>& l) : open_list(l)
659    {}
660    InheritanceAdder(const InheritanceAdder& i) : open_list(i.open_list)
661    {}
662    void operator() (ASG::Inheritance* i)
663    {
664        try
665        {
666            open_list.push_back(Types::declared_cast<ASG::Class>(i->parent()));
667        }
668        catch (const Types::wrong_type_cast&)
669        { /* ?? ignore for now */
670        }
671    }
672};
673
674
675//. Maps a scoped name into a vector of scopes and the final type. Returns
676//. true on success.
677bool Builder::mapName(const ScopedName& names, std::vector<ASG::Scope*>& o_scopes, Types::Named*& o_type)
678{
679    STrace trace("Builder::mapName");
680    ASG::Scope* ast_scope = m_global;
681    ScopedName::const_iterator iter = names.begin();
682    ScopedName::const_iterator last = names.end();
683    last--;
684    ScopedName scoped_name;
685
686    // Start scope name at global level
687    scoped_name.push_back("");
688
689    // Sanity check
690    if (iter == names.end())
691        return false;
692
693    // Loop through all containing scopes
694    while (iter != last)
695    {
696        //const std::string& name = *iter++;
697        scoped_name.push_back(*iter++);
698        Types::Named* type = m_lookup->lookupType(scoped_name);
699        if (!type)
700        {
701            LOG("Warning: failed to lookup " << scoped_name << " in global scope");
702            return false;
703        }
704        try
705        {
706            ast_scope = Types::declared_cast<ASG::Scope>(type);
707        }
708        catch (const Types::wrong_type_cast&)
709        {
710            LOG("Warning: looked up scope wasnt a scope!" << scoped_name);
711            return false;
712        }
713        o_scopes.push_back(ast_scope);
714    }
715
716    // iter now == last, which can be any type
717    scoped_name.push_back(*iter);
718    Types::Named* type = m_lookup->lookupType(scoped_name, true);
719    if (!type)
720    {
721        //find_info(ast_scope)->dict->dump();
722        LOG("\nWarning: final type lookup wasn't found!" << *iter);
723        return false;
724    }
725
726    o_type = type;
727    return true;
728}
729
730
731Types::Unknown* Builder::create_unknown(const ScopedName& name)
732{
733    // Generate the name
734    ScopedName u_name = m_scope->name();
735    for (ScopedName::const_iterator i = name.begin(); i != name.end(); ++i)
736      u_name.push_back(*i);
737    Types::Unknown* unknown = new Types::Unknown(u_name);
738    return unknown;
739}
740
741Types::Unknown* Builder::add_unknown(const std::string& name)
742{
743    if (m_scopes.back()->dict->has_key(name) == false)
744    {
745      ScopedName u_name;
746      u_name.push_back(name);
747      add(create_unknown(u_name));
748    }
749    return 0;
750}
751
752ASG::Forward* Builder::add_forward(int lineno, const std::string& name, const std::string &type,
753                                   ASG::Parameter::vector* templ_params)
754{
755  ScopeInfo* parent_scope = templ_params ? 
756    // Must find the scope above the template scope
757    m_scopes[m_scopes.size() - 2] : 
758    m_scopes[m_scopes.size() - 1];
759  ScopedName scoped_name = extend(parent_scope->scope_decl->name(), name);
760  // The type is already known.
761  if (parent_scope->dict->has_key(name) == true) return 0;
762  bool is_template = templ_params && templ_params->size();
763  bool is_specialization = *name.rbegin() == '>';
764  ASG::Forward* forward = new ASG::Forward(m_file, lineno, type, scoped_name, is_specialization);
765  if (is_template)
766  {
767    Types::Template* templ = new Types::Template(scoped_name, forward, *templ_params);
768    forward->set_template_id(templ);
769  }
770  add(forward, templ_params != 0);
771  return forward;
772}
773
774Types::Base* Builder::create_base(const std::string& name)
775{
776    return new Types::Base(extend(m_scope->name(), name));
777}
778
779Types::Dependent* Builder::create_dependent(const std::string& name)
780{
781    return new Types::Dependent(extend(m_scope->name(), name));
782}
783
784std::string Builder::dump_search(ScopeInfo* scope)
785{
786    ScopeSearch& search = scope->search;
787    std::ostringstream buf;
788    buf << "Search for ";
789    if (scope->scope_decl->name().size() == 0)
790        buf << "global";
791    else
792        buf << m_scope->name();
793    buf << " is now: ";
794    ScopeSearch::iterator iter = search.begin();
795    while (iter != search.end())
796    {
797        buf << (iter==search.begin() ? "" : ", ");
798        const ScopedName& name = (*iter)->scope_decl->name();
799        if (name.size())
800            if ( (*iter)->is_using )
801                buf << "(" << name << ")";
802            else
803                buf << name;
804        else
805            buf << "global";
806        ++iter;
807    }
808    //buf << std::ends;
809    return buf.str();
810}
811
812// A comparator which compares declaration pointers of ScopeInfo objects
813class Builder::EqualScope
814{
815    ASG::Scope* target;
816public:
817    EqualScope(ScopeInfo* t)
818    {
819        target = t->scope_decl;
820    }
821    bool operator()(ScopeInfo* s)
822    {
823        return s->scope_decl == target;
824    }
825};
826
827void Builder::do_add_using_directive(ScopeInfo* target, ScopeInfo* scope)
828{
829    STrace trace("Builder::do_add_using_directive");
830
831    // Check if 'scope' already has 'target' in its using list
832    ScopeSearch& uses = scope->using_scopes;
833    if (std::find_if(uses.begin(), uses.end(), EqualScope(target)) != uses.end())
834        // Already using
835        return;
836    // Else add it
837    scope->using_scopes.push_back(target);
838    target->used_by.push_back(scope);
839
840    ScopedName& target_name = target->scope_decl->name();
841
842    // Find where to insert 'scope' into top()'s search list
843    // "closest enclosing namespace that contains both using directive and
844    //  target namespace" -- C++ Standard
845    ScopeSearch& search = scope->search;
846    LOG(dump_search(scope));
847    ScopeSearch::iterator iter = search.end();
848    // Skip global scope.. cant check something with no name
849    --iter;
850    while (iter != search.begin())
851    {
852        // Move to next scope to check
853        --iter;
854        ScopedName& search_name = (*iter)->scope_decl->name();
855        if (target_name.size() < search_name.size())
856            // Search is more nested than the target
857            break;
858        if (search_name.size() < 1)
859            // Global NS..
860            continue;
861        if (target_name[search_name.size()-1] != search_name.back())
862            // Different scope path taken
863            break;
864    }
865    // Move back to last which was common, so we can insert before it
866    if (*iter != search.back() && iter != search.begin())
867        iter++;
868
869    // Create a dummy ScopeInfo which is just an alias to the original. This
870    // is needed to cumulate using namespaces in the lookups
871    ScopeInfo* new_scope = new ScopeInfo(target);
872    search.insert(iter, new_scope);
873
874    LOG(dump_search(scope));
875
876    // Add target to all used_by scopes
877    ScopeSearch used_by_copy = scope->used_by;
878    iter = used_by_copy.begin();
879    while (iter != used_by_copy.end())
880        do_add_using_directive(target, *iter++);
881}
882
883// Add a namespace using declaration.
884ASG::UsingDirective *Builder::add_using_directive(int line, Types::Named* type)
885{
886    STrace trace("Builder::using_directive");
887    ASG::Scope* ast_scope = Types::declared_cast<ASG::Scope>(type);
888    ScopeInfo* target = find_info(ast_scope);
889    do_add_using_directive(target, m_scopes.back());
890    
891    ASG::UsingDirective* u = new ASG::UsingDirective(m_file, line, type->name());
892    add(u);
893    return u;
894}
895
896
897// Add a namespace alias using declaration.
898void Builder::add_aliased_using_namespace(Types::Named* type, const std::string& alias)
899{
900    STrace trace("Builder::usingNamespace");
901
902    // Retrieve the 'Namespace' it points to
903    ASG::Namespace* ns = Types::declared_cast<ASG::Namespace>(type);
904
905    // Create a new declared type with a different name
906    ScopedName new_name = extend(m_scope->name(), alias);
907    Types::Declared* declared = new Types::Declared(new_name, ns);
908
909    // Add to current scope
910    add(declared);
911}
912
913// Add a using declaration.
914ASG::UsingDeclaration *Builder::add_using_declaration(int line, Types::Named* type)
915{
916    // Add it to the current scope
917    ScopedName name = extend(m_scope->name(), type->name().back());
918    ASG::UsingDeclaration* u = new ASG::UsingDeclaration(m_file, line, name, type);
919    add(u);
920    return u;
921}