---

walker.cc

Go to the documentation of this file.

/*
  Copyright (C) 1997-2001 Shigeru Chiba, Tokyo Institute of Technology.

  Permission to use, copy, distribute and modify this software and   
  its documentation for any purpose is hereby granted without fee,        
  provided that the above copyright notice appear in all copies and that 
  both that copyright notice and this permission notice appear in 
  supporting documentation.

  Shigeru Chiba makes no representations about the suitability of this 
  software for any purpose.  It is provided "as is" without express or
  implied warranty.
*/

#include <string.h>
#include "env.h"
#include "ptree.h"
#include "walker.h"
#include "typeinfo.h"
#include "mop.h"
#include "metaclass.h"
#include "parse.h"
#include "encoding.h"
#include "member.h"

Parser* Walker::default_parser = nil;
char* Walker::argument_name = "_arg_%d_";
char* Walker::default_metaclass = nil;

Walker::Walker(Parser* p)
{
    env = new Environment(this);
    parser = p;
    if(default_parser == nil)
        default_parser = p;
}

Walker::Walker(Parser* p, Environment* e)
{
    env = new Environment(e, this);
    parser = p;
    if(default_parser == nil)
        default_parser = p;
}

Walker::Walker(Environment* e)
{
    env = new Environment(e, this);
    if(default_parser == nil)
        MopErrorMessage("Walker::Walker()", "no default parser");

    parser = default_parser;
}

Walker::Walker(Walker* w)
{
    env = w->env;
    parser = w->parser;
}

void Walker::NewScope()
{
    env = new Environment(env);
}

void Walker::NewScope(Environment* e)
{
    if (e != nil)
        env = e;
    else
        env = new Environment(env);
}

void Walker::NewScope(Class* metaobject)
{
    env = new Environment(env);
    if(metaobject != nil)
        metaobject->SetEnvironment(env);
}

Environment* Walker::ExitScope()
{
    Environment* old_env = env;
    env = old_env->GetOuterEnvironment();
    return old_env;
}

void Walker::RecordBaseclassEnv(Ptree* bases)
{
    while(bases != nil){
        bases = bases->Cdr();           // skip : or ,
        Ptree* base_class = bases->Car()->Last()->Car();
        Class* metaobject = env->LookupClassMetaobject(base_class);
        if(metaobject != nil){
            Environment* e = metaobject->GetEnvironment();
            if(e != nil)
                env->AddBaseclassEnv(e);
        }

        bases = bases->Cdr();
    }
}

Walker::NameScope Walker::ChangeScope(Environment* e)
{
    NameScope scope;
    scope.walker = e->GetWalker();
    e->SetWalker(this);
    scope.env = env;
    env = e;
    return scope;
}

void Walker::RestoreScope(Walker::NameScope& scope)
{
    env->SetWalker(scope.walker);
    env = scope.env;
}

bool Walker::IsClassWalker()
{
    return FALSE;
}

Ptree* Walker::Translate(Ptree* p)
{
    if(p == nil)
        return p;
    else
        return p->Translate(this);
}

void Walker::Typeof(Ptree* p, TypeInfo& t)
{
    if(p != nil)
        p->Typeof(this, t);
}

// default translation

Ptree* Walker::TranslatePtree(Ptree* p)
{
    return p;
}

void Walker::TypeofPtree(Ptree*, TypeInfo& t)
{
    t.Unknown();
}

// translation for each class of node

Ptree* Walker::TranslateTypedef(Ptree* def)
{
    Ptree *tspec, *tspec2;

    tspec = Ptree::Second(def);
    tspec2 = TranslateTypespecifier(tspec);
    env->RecordTypedefName(Ptree::Third(def));
    if(tspec == tspec2)
        return def;
    else
        return new PtreeTypedef(Ptree::First(def),
                                Ptree::List(tspec2,
                                            Ptree::ListTail(def, 2)));
}

Ptree* Walker::TranslateTemplateDecl(Ptree* def)
{
    Ptree* body = Ptree::Nth(def, 4);
    Ptree* class_spec = GetClassTemplateSpec(body);
    if(class_spec->IsA(ntClassSpec))
        return TranslateTemplateClass(def, class_spec);
    else
        return TranslateTemplateFunction(def, body);
}

Ptree* Walker::TranslateExternTemplate(Ptree* def)
{
    return def;
}

Ptree* Walker::TranslateTemplateClass(Ptree* temp_def, Ptree* class_spec)
{
    Ptree* userkey;
    Ptree* class_def;

    if(class_spec->Car()->IsLeaf()){
        userkey = nil;
        class_def = class_spec;
    }
    else{
        userkey = class_spec->Car();
        class_def = class_spec->Cdr();
    }

    Class* metaobject = nil;
    if(Ptree::Length(class_def) == 4)
        metaobject = MakeTemplateClassMetaobject(temp_def, userkey, class_def);

    env->RecordTemplateClass(class_spec, metaobject);
    Ptree* class_spec2 = TranslateClassSpec(class_spec, userkey, class_def,
                                            metaobject);
    if(class_spec == class_spec2)
        return temp_def;
    else
        return new PtreeTemplateDecl(temp_def->Car(),
                                     Ptree::Subst(class_spec2, class_spec,
                                                  temp_def->Cdr()));
}

Class* Walker::MakeTemplateClassMetaobject(Ptree* def, Ptree* userkey,
                                           Ptree* class_def)
{
    Class* metaobject = LookupMetaclass(def, userkey, class_def, TRUE);
    if(metaobject == nil)
        metaobject = new TemplateClass;
    else
        if(metaobject->AcceptTemplate())
            return metaobject;
        else{

            ErrorMessage("the specified metaclass is not for templates.",
                         nil, def);
            metaobject = new TemplateClass;
        }

    metaobject->InitializeInstance(def, nil);
    return metaobject;
}

Ptree* Walker::TranslateTemplateFunction(Ptree* temp_def, Ptree* fun)
{
    env->RecordTemplateFunction(temp_def, fun);
    return temp_def;
}

Ptree* Walker::TranslateTemplateInstantiation(Ptree *inst_spec)
{
    Ptree* userkey;
    Ptree* class_spec;
    Ptree* full_class_spec = Ptree::First(inst_spec);

    if(full_class_spec->Car()->IsLeaf()){
        userkey = nil;
        class_spec = full_class_spec;
    }
    else{
        userkey = full_class_spec->Car();
        class_spec = full_class_spec->Cdr();
    }

    Class* metaobject = nil;
    metaobject = MakeTemplateInstantiationMetaobject(full_class_spec,
                                                     userkey, class_spec);
    return TranslateTemplateInstantiation(inst_spec, userkey, 
                                          class_spec, metaobject);
}

Class* Walker::MakeTemplateInstantiationMetaobject(
    Ptree* full_class_spec, Ptree* userkey, Ptree* class_spec)
{
    // [class [foo [< ... >]]] -> [class foo]
    Ptree* class_name = Ptree::First(Ptree::Second(class_spec));
    Bind* binding = nil;
    if (!env->Lookup(class_name,binding))
        return nil;

    Class* metaobject = nil;
    if (binding->What() != Bind::isTemplateClass) {
        ErrorMessage("not declarated as a template class?!?",
                     nil, full_class_spec);
        metaobject = nil;
    }
    else
        metaobject = binding->ClassMetaobject();

    if (metaobject == nil)
        metaobject = new TemplateClass;
    else
        if(metaobject->AcceptTemplate())
            return metaobject;
        else{
            ErrorMessage("the specified metaclass is not for templates.",
                         nil, full_class_spec);
            metaobject = new TemplateClass;
        }

    return metaobject;
}

Ptree* Walker::TranslateTemplateInstantiation(Ptree* inst_spec,
                Ptree* userkey, Ptree* class_spec, Class* metaobject)
{
    if (metaobject == nil)
        return inst_spec;
    else {
        Ptree *class_spec2 = TranslateClassSpec(class_spec);
        if (class_spec == class_spec2)
            return inst_spec;
        else
            return class_spec2;
    }
}

Ptree* Walker::TranslateMetaclassDecl(Ptree* decl)
{
    env->RecordMetaclassName(decl);
    return decl;
}

Ptree* Walker::TranslateLinkageSpec(Ptree* def)
{
    Ptree* body = Ptree::Third(def);
    Ptree* body2 = Translate(body);
    if(body == body2)
        return def;
    else
        return new PtreeLinkageSpec(Ptree::First(def),
                                    Ptree::List(Ptree::Second(def),
                                                body2));
}

Ptree* Walker::TranslateNamespaceSpec(Ptree* def)
{
    Ptree* name = Ptree::Second(def);
    Ptree* body = Ptree::Third(def);

    Environment* name_space = env->LookupNamespace0(name);
    NewScope(name_space);
    Ptree* body2 = Translate(body);
    Environment* name_space2 = ExitScope();

    if (name_space == nil)      // if this is the first time
        env->RecordNamespace(name_space2, name);

    if(body == body2)
        return def;
    else
        return new PtreeNamespaceSpec(Ptree::First(def),
                                      Ptree::List(name, body2));
}

Ptree* Walker::TranslateUsing(Ptree* def)
{
    if (((PtreeUsing*)def)->isNamespace())
        env->RecordUsingNamespace(def);
    else
        env->RecordUsing(def);

    return def;
}

Ptree* Walker::TranslateDeclaration(Ptree* def)
{
    Ptree* decls = Ptree::Third(def);
    if(decls->IsA(ntDeclarator))        // if it is a function
        return TranslateFunctionImplementation(def);
    else{
        // if it is a function prototype or a variable declaration.
        Ptree* decls2;
        Ptree* sspec = Ptree::First(def);
        Ptree* sspec2 = TranslateStorageSpecifiers(sspec);
        Ptree* tspec = Ptree::Second(def);
        Ptree* tspec2 = TranslateTypespecifier(tspec);
        if(decls->IsLeaf())     // if it is ";"
            decls2 = decls;
        else
            decls2 = TranslateDeclarators(decls);

        if(sspec == sspec2 && tspec == tspec2 && decls == decls2)
            return def;
        else if(decls2 == nil)
            return new PtreeDeclaration(nil, Ptree::List(nil,
                                                         Class::semicolon_t));
        else
            return new PtreeDeclaration(sspec2,
                                        Ptree::ShallowSubst(tspec2, tspec,
                                                            decls2, decls,
                                                            def->Cdr()));
    }
}

// TranslateStorageSpecifiers() also deals with inline, virtual, etc.

Ptree* Walker::TranslateStorageSpecifiers(Ptree* spec)
{
    return spec;
}

Ptree* Walker::TranslateDeclarators(Ptree* decls)
{
    return TranslateDeclarators(decls, TRUE);
}

Ptree* Walker::TranslateDeclarators(Ptree* decls, bool record)
{
    PtreeArray array;
    bool changed = FALSE;
    Ptree* rest = decls;
    while(rest != nil){
        Ptree *p, *q;
        int len;
        p = q = rest->Car();
        if(p->IsA(ntDeclarator)){
            Ptree *exp, *exp2;

            if(record)
                env->RecordDeclarator(p);

            len = p->Length();
            exp = exp2 = nil;
            if(len >= 2 && p->Nth(len - 2)->Eq('=')){
                exp = p->ListTail(len - 2);
                exp2 = TranslateAssignInitializer((PtreeDeclarator*)p, exp);
            }
            else{
                Ptree* last = p->Last()->Car();
                if(last != nil && !last->IsLeaf() && last->Car()->Eq('(')){
                    exp = last;
                    exp2 = TranslateInitializeArgs((PtreeDeclarator*)p, last);
                }
            }

            q = TranslateDeclarator(FALSE, (PtreeDeclarator*)p);
            if(exp != exp2){
                // exp2 should be a list, but...
                if(exp2 != nil && exp2->IsLeaf())
                    exp2 = Ptree::List(exp2);

                if(p == q){
                    q = Ptree::SubstSublist(exp2, exp, p->Cdr());
                    q = new PtreeDeclarator((PtreeDeclarator*)p, p->Car(), q);
                }
                else if(q != nil && !q->IsLeaf())
                    q = new PtreeDeclarator((PtreeDeclarator*)p, q->Car(),
                                            Ptree::Subst(exp2, exp, q->Cdr()));
            }
        }

        if(q == nil){
            changed = TRUE;
            rest = rest->Cdr();
            if(rest != nil)
                rest = rest->Cdr();
        }
        else{
            array.Append(q);
            if(p != q)
                changed = TRUE;

            rest = rest->Cdr();
            if(rest != nil){
                array.Append(rest->Car());
                rest = rest->Cdr();
            }
        }
    }

    if(changed)
        return array.All();
    else
        return decls;
}

Ptree* Walker::TranslateDeclarator(bool record, PtreeDeclarator* decl)
{
    // if record is true, the formal arguments are recorded in the
    // current environment.

    Ptree* args;
    if(GetArgDeclList(decl, args)){
        Ptree* args2 = TranslateArgDeclList(record, decl, args);
        if(args == args2)
            return decl;
        else
            return new PtreeDeclarator(decl, decl->Car(),
                                       Ptree::Subst(args2, args,
                                                    decl->Cdr()));
    }
    else
        return decl;
}

bool Walker::GetArgDeclList(PtreeDeclarator* decl, Ptree*& args)
{
    Ptree* p = decl;
    while(p != nil){
        Ptree* q = p->Car();
        if(q != nil)
            if(q->IsLeaf()){
                if(q->Eq('(')){
                    args = p->Cadr();
                    return TRUE;
                }
            }
            else if(q->Car()->Eq('('))  // e.g. int (*p)[];
                p = q->Cadr();

        p = p->Cdr();
    }

    args = nil;
    return FALSE;
}

Ptree* Walker::TranslateArgDeclList(bool record, Ptree*, Ptree* args)
{
    return TranslateArgDeclList2(record, env, FALSE, FALSE, 0, args);
}

// If translate is TRUE, this function eliminates a user-defined keyword.

Ptree* Walker::TranslateArgDeclList2(bool record, Environment* e,
                                     bool translate,
                                     bool fill_args, int arg_name,
                                     Ptree* args)
{
    Ptree* rest;
    Ptree* rest2;

    if(args == nil)
        return args;
    else{
        Ptree *a, *a2;
        a = a2 = args->Car();
        if(args->Cdr() == nil)
            rest = rest2 = nil;
        else{
            rest = args->Cddr();        // skip ","
            rest2 = TranslateArgDeclList2(record, e, translate, fill_args,
                                          arg_name + 1, rest);
            if(rest == rest2)
                rest = rest2 = args->Cdr();
            else
                rest2 = Ptree::Cons(args->Cadr(), rest2);
        }

        bool is_ellipsis = a->IsLeaf();         // a may be "..."
        if(is_ellipsis)
            /* do nothing */;
        else if(a->Car()->IsA(ntUserdefKeyword)){
            if(record)
                e->RecordDeclarator(a->Third());

            if(translate){
                a2 = a->Cdr();
                if(fill_args)
                    a2 = FillArgumentName(a2, a2->Second(), arg_name);
            }
        }
        else if(a->Car()->IsA(REGISTER)){
            if(record)
                e->RecordDeclarator(a->Third());

            if(translate && fill_args){
                a2 = FillArgumentName(a, a->Third(), arg_name);
                if(a != a2)
                    a2 = Ptree::Cons(a->First(), a2);
            }
        }
        else{
            if(record)
                e->RecordDeclarator(a->Second());

            if(translate && fill_args)
                a2 = FillArgumentName(a, a->Second(), arg_name);
        }

        if(a != a2 || rest != rest2)
            return Ptree::Cons(a2, rest2);
        else
            return args;
    }
}

Ptree* Walker::FillArgumentName(Ptree* arg, Ptree* d, int arg_name)
{
    PtreeDeclarator* decl = (PtreeDeclarator*)d;
    if(decl->Name() != nil)
        return arg;
    else{
        unsigned char* type = (unsigned char*)decl->GetEncodedType();
        return Encoding::MakePtree(type,
                                   Ptree::Make(argument_name, arg_name));
    }
}

Ptree* Walker::TranslateAssignInitializer(PtreeDeclarator*, Ptree* init)
{
    Ptree* exp = init->Second();
    Ptree* exp2 = Translate(exp);
    if(exp == exp2)
        return init;
    else
        return Ptree::List(init->Car(), exp2);
}

Ptree* Walker::TranslateInitializeArgs(PtreeDeclarator*, Ptree* init)
{
    return TranslateArguments(init);
}

Ptree* Walker::TranslateFunctionImplementation(Ptree* impl)
{
    Ptree* sspec = Ptree::First(impl);
    Ptree* sspec2 = TranslateStorageSpecifiers(sspec);
    Ptree* tspec = Ptree::Second(impl);
    Ptree* decl = Ptree::Third(impl);
    Ptree* body = Ptree::Nth(impl, 3);
    Ptree* decl2;
    Ptree* body2;

    Ptree* tspec2 = TranslateTypespecifier(tspec);
    Environment* fenv = env->RecordDeclarator(decl);
    if(fenv == nil){
        // reach here if resolving the qualified name fails. error?
        NewScope();
        decl2 = TranslateDeclarator(TRUE, (PtreeDeclarator*)decl);
        body2 = Translate(body);
        ExitScope();
    }
    else{
        NameScope old_env = ChangeScope(fenv);
        NewScope();
        decl2 = TranslateDeclarator(TRUE, (PtreeDeclarator*)decl);
        body2 = Translate(body);
        ExitScope();
        RestoreScope(old_env);
    }

    if(sspec == sspec2 && tspec == tspec2 && decl == decl2 && body == body2)
        return impl;
    else
        return new PtreeDeclaration(sspec2,
                                    Ptree::List(tspec2, decl2, body2));
}

Ptree* Walker::RecordArgsAndTranslateFbody(Class*, Ptree* args, Ptree* body)
{
    NewScope();
    TranslateArgDeclList2(TRUE, env, FALSE, FALSE, 0, args);
    Ptree* body2 = TranslateFunctionBody(body);
    ExitScope();
    return body2;
}

Ptree* Walker::TranslateFunctionBody(Ptree* body)
{
    return Translate(body);
}

Ptree* Walker::TranslateBrace(Ptree* block)
{
    PtreeArray array;
    bool changed = FALSE;
    Ptree* body = Ptree::Second(block);
    Ptree* rest = body;
    while(rest != nil){
        Ptree* p = rest->Car();
        Ptree* q = Translate(p);
        array.Append(q);
        if(p != q)
            changed = TRUE;

        rest = rest->Cdr();
    }

    if(changed)
        return new PtreeBrace(Ptree::First(block), array.All(),
                              Ptree::Third(block));
    else
        return block;
}

Ptree* Walker::TranslateBlock(Ptree* block)
{
    Ptree* block2;

    NewScope();

    PtreeArray array;
    bool changed = FALSE;
    Ptree* body = Ptree::Second(block);
    Ptree* rest = body;
    while(rest != nil){
        Ptree* p = rest->Car();
        Ptree* q = Translate(p);
        array.Append(q);
        if(p != q)
            changed = TRUE;

        rest = rest->Cdr();
    }

    if(changed)
        block2 = new PtreeBlock(Ptree::First(block), array.All(),
                                Ptree::Third(block));
    else
        block2 = block;

    ExitScope();
    return block2;
}

Ptree* Walker::TranslateClassBody(Ptree* block, Ptree* bases,
                                  Class* metaobject)
{
    Ptree* block2;

    NewScope(metaobject);
    RecordBaseclassEnv(bases);

    PtreeArray array;
    bool changed = FALSE;
    Ptree* body = Ptree::Second(block);
    Ptree* rest = body;
    while(rest != nil){
        Ptree* p = rest->Car();
        Ptree* q = Translate(p);
        array.Append(q);
        if(p != q)
            changed = TRUE;

        rest = rest->Cdr();
    }

    if(changed)
        block2 = new PtreeClassBody(Ptree::First(block), array.All(),
                                    Ptree::Third(block));
    else
        block2 = block;

    ExitScope();
    return block2;
}

Ptree* Walker::TranslateClassSpec(Ptree* spec)
{
    Ptree* userkey;
    Ptree* class_def;

    if(spec->Car()->IsLeaf()){
        userkey = nil;
        class_def = spec;
    }
    else{
        userkey = spec->Car();
        class_def = spec->Cdr();
    }

    Class* metaobject = nil;
    if(Ptree::Length(class_def) == 4)
        metaobject = MakeClassMetaobject(spec, userkey, class_def);

    env->RecordClassName(spec->GetEncodedName(), metaobject);
    return TranslateClassSpec(spec, userkey, class_def, metaobject);
}

Class* Walker::MakeClassMetaobject(Ptree* def, Ptree* userkey,
                                   Ptree* class_def)
{
    Class* metaobject = LookupMetaclass(def, userkey, class_def, FALSE);
    if(metaobject == nil && default_metaclass != nil){
        metaobject = opcxx_ListOfMetaclass::New(default_metaclass, class_def,
                                                nil);
        if(metaobject == nil)
            MopErrorMessage2("the default metaclass cannot be loaded: ",
                             default_metaclass);
    }

    if(metaobject == nil)
        metaobject = new Class;
    else{
        if(!metaobject->AcceptTemplate())
            return metaobject;
        else{
            ErrorMessage("the specified metaclass is for templates.",
                         nil, def);
            metaobject = new Class;
        }
    }

    metaobject->InitializeInstance(class_def, nil);
    return metaobject;
}

void Walker::ChangeDefaultMetaclass(char* name)
{
    default_metaclass = name;
}

// LookupMetaclass() returns nil if no metaclass is found.

Class* Walker::LookupMetaclass(Ptree* def, Ptree* userkey, Ptree* class_def,
                               bool is_template)
{
    Ptree *mclass, *margs;
    Class* metaobject;

    Ptree* class_name = class_def->Second();

    // for bootstrapping
    if(Metaclass::IsBuiltinMetaclass(class_name)){
        metaobject = new Metaclass;
        metaobject->InitializeInstance(def, nil);
        return metaobject;
    }

    Ptree* mdecl = env->LookupMetaclass(class_name);
    if(mdecl != nil){
        mclass = mdecl->Second();
        margs = mdecl->Nth(4);
        metaobject = opcxx_ListOfMetaclass::New(mclass, def, margs);
        if(metaobject == nil)
            ErrorMessage("the metaclass is not loaded: ", mclass, class_def);
        else if(userkey != nil)
            ErrorMessage("the metaclass declaration conflicts"
                         " with the keyword: ", mclass, class_def);

        return metaobject;
    }

    if(userkey != nil){
        mclass = env->LookupClasskeyword(userkey->Car());
        if(mclass == nil)
            ErrorMessage("invalid keyword: ", userkey, class_def);
        else{
            metaobject = opcxx_ListOfMetaclass::New(mclass, class_def,
                                                    userkey->Third());
            if(metaobject == nil)
                ErrorMessage("the metaclass associated with the"
                             " keyword is not loaded: ", userkey, class_def);

            return metaobject;
        }
    }

    return LookupBaseMetaclass(def, class_def, is_template);
}

Class* Walker::LookupBaseMetaclass(Ptree* def, Ptree* class_def,
                                   bool is_template)
{
    Class* metaobject = nil;
    Ptree* bases = class_def->Third();
    while(bases != nil){
        bases = bases->Cdr();
        Ptree* base = bases->Car()->Last()->Car();
        bases = bases->Cdr();
        Class* m = env->LookupClassMetaobject(base);
        if(m != nil){
            if(metaobject == nil)
                metaobject = m;
            else if(m == nil || strcmp(metaobject->MetaclassName(),
                                       m->MetaclassName()) != 0){
                ErrorMessage("inherited metaclasses conflict: ",
                             class_def->Second(), class_def);
                return nil;
            }
        }
    }

    if(metaobject == nil)
        return nil;

    bool accept_template = metaobject->AcceptTemplate();
    if((is_template && accept_template) || (!is_template && !accept_template))
        return opcxx_ListOfMetaclass::New(metaobject->MetaclassName(),
                                          def, nil);
    else
        return nil;
}

Ptree* Walker::TranslateClassSpec(Ptree* spec, Ptree*,
                                  Ptree* class_def, Class* metaobject)
{
    if(metaobject == nil)
        return spec;
    else{
        // a class body is specified.
        Ptree* body = class_def->Nth(3);
        Ptree* body2 = TranslateClassBody(body, class_def->Third(),
                                          metaobject);
        if(body == body2)
            return spec;
        else
            return new PtreeClassSpec(spec->Car(),
                                      Ptree::ShallowSubst(body2, body,
                                                          spec->Cdr()),
                                      nil, spec->GetEncodedName());
    }
}


Ptree* Walker::TranslateEnumSpec(Ptree* spec)
{
    env->RecordEnumName(spec);
    return spec;
}

Ptree* Walker::TranslateAccessSpec(Ptree* p)
{
    return p;
}

Ptree* Walker::TranslateAccessDecl(Ptree* p)
{
    return p;
}

Ptree* Walker::TranslateUserAccessSpec(Ptree* p)
{
    return p;
}

Ptree* Walker::TranslateIf(Ptree* s)
{
    Ptree* cond = s->Third();
    Ptree* cond2 = Translate(cond);
    Ptree* then_part = s->Nth(4);
    Ptree* then_part2 = Translate(then_part);
    Ptree* else_part = s->Nth(6);
    Ptree* else_part2 = Translate(else_part);

    if(cond == cond2 && then_part == then_part2 && else_part == else_part2)
        return s;
    else{
        Ptree* rest = Ptree::ShallowSubst(cond2, cond, then_part2, then_part,
                                          else_part2, else_part, s->Cdr());
        return new PtreeIfStatement(s->Car(), rest);
    }
}

Ptree* Walker::TranslateSwitch(Ptree* s)
{
    Ptree* cond = s->Third();
    Ptree* cond2 = Translate(cond);
    Ptree* body = s->Nth(4);
    Ptree* body2 = Translate(body);
    if(cond == cond2 && body == body2)
        return s;
    else{
        Ptree* rest = Ptree::ShallowSubst(cond2, cond, body2, body, s->Cdr());
        return new PtreeSwitchStatement(s->Car(), rest);
    }
}

Ptree* Walker::TranslateWhile(Ptree* s)
{
    Ptree* cond = s->Third();
    Ptree* cond2 = Translate(cond);
    Ptree* body = s->Nth(4);
    Ptree* body2 = Translate(body);
    if(cond == cond2 && body == body2)
        return s;
    else{
        Ptree* rest = Ptree::ShallowSubst(cond2, cond, body2, body, s->Cdr());
        return new PtreeWhileStatement(s->Car(), rest);
    }
}

Ptree* Walker::TranslateDo(Ptree* s)
{
    Ptree* body = s->Second();
    Ptree* body2 = Translate(body);
    Ptree* cond = s->Nth(4);
    Ptree* cond2 = Translate(cond);
    if(cond == cond2 && body == body2)
        return s;
    else{
        Ptree* rest = Ptree::ShallowSubst(body2, body, cond2, cond, s->Cdr());
        return new PtreeDoStatement(s->Car(), rest);
    }
}

Ptree* Walker::TranslateFor(Ptree* s)
{
    NewScope();
    Ptree* exp1 = s->Third();
    Ptree* exp1t = Translate(exp1);
    Ptree* exp2 = s->Nth(3);
    Ptree* exp2t = Translate(exp2);
    Ptree* exp3 = s->Nth(5);
    Ptree* exp3t = Translate(exp3);
    Ptree* body = s->Nth(7);
    Ptree* body2 = Translate(body);
    ExitScope();

    if(exp1 == exp1t && exp2 == exp2t && exp3 == exp3t && body == body2)
        return s;
    else{
        Ptree* rest = Ptree::ShallowSubst(exp1t, exp1, exp2t, exp2,
                                          exp3t, exp3, body2, body, s->Cdr());
        return new PtreeForStatement(s->Car(), rest);
    }
}

Ptree* Walker::TranslateTry(Ptree* s)
{
    Ptree* try_block = s->Second();
    Ptree* try_block2 = Translate(try_block);

    PtreeArray array;
    Ptree* handlers = s->Cddr();
    bool changed = FALSE;

    while(handlers != nil){
        Ptree* handle = handlers->Car();
        Ptree* body = handle->Nth(4);
        Ptree* body2 = Translate(body);
        if(body == body2)
            array.Append(handle);
        else{
            array.Append(Ptree::ShallowSubst(body2, body, handle));
            changed = TRUE;
        }

        handlers = handlers->Cdr();
    }

    if(try_block == try_block2 && !changed)
        return s;
    else
        return new PtreeTryStatement(s->Car(),
                                     Ptree::Cons(try_block2, array.All()));
}

Ptree* Walker::TranslateBreak(Ptree* s)
{
    return s;
}

Ptree* Walker::TranslateContinue(Ptree* s)
{
    return s;
}

Ptree* Walker::TranslateReturn(Ptree* s)
{
    if(s->Length() == 2)
        return s;
    else{
        Ptree* exp = s->Second();
        Ptree* exp2 = Translate(exp);
        if(exp == exp2)
            return s;
        else
            return new PtreeReturnStatement(s->Car(),
                                            Ptree::ShallowSubst(exp2, exp,
                                                                s->Cdr()));
    }
}

Ptree* Walker::TranslateGoto(Ptree* s)
{
    return s;
}

Ptree* Walker::TranslateCase(Ptree* s)
{
    Ptree* st = s->Nth(3);
    Ptree* st2 = Translate(st);
    if(st == st2)
        return s;
    else
        return new PtreeCaseStatement(s->Car(),
                                      Ptree::ShallowSubst(st2, st, s->Cdr()));
}

Ptree* Walker::TranslateDefault(Ptree* s)
{
    Ptree* st = s->Third();
    Ptree* st2 = Translate(st);
    if(st == st2)
        return s;
    else
        return new PtreeDefaultStatement(s->Car(),
                                         Ptree::List(s->Cadr(), st2));
}

Ptree* Walker::TranslateLabel(Ptree* s)
{
    Ptree* st = s->Third();
    Ptree* st2 = Translate(st);
    if(st == st2)
        return s;
    else
        return new PtreeLabelStatement(s->Car(),
                                       Ptree::List(s->Cadr(), st2));
}

Ptree* Walker::TranslateExprStatement(Ptree* s)
{
    Ptree* exp = s->First();
    Ptree* exp2 = Translate(exp);
    if(exp == exp2)
        return s;
    else
        return new PtreeExprStatement(exp2, s->Cdr());
}

Ptree* Walker::TranslateTypespecifier(Ptree* tspec)
{
    Ptree *class_spec, *class_spec2;

    class_spec = GetClassOrEnumSpec(tspec);
    if(class_spec == nil)
        class_spec2 = nil;
    else
        class_spec2 = Translate(class_spec);

    if(class_spec == class_spec2)
        return tspec;
    else
        return Ptree::ShallowSubst(class_spec2, class_spec, tspec);
}

Ptree* Walker::GetClassOrEnumSpec(Ptree* typespec)
{
    Ptree* spec = StripCvFromIntegralType(typespec);
    if(spec->IsA(ntClassSpec, ntEnumSpec))
        return spec;

    return nil;
}

Ptree* Walker::GetClassTemplateSpec(Ptree* body)
{
    if(Ptree::Eq(Ptree::Third(body), ';')){
        Ptree* spec = StripCvFromIntegralType(Ptree::Second(body));
        if(spec->IsA(ntClassSpec))
            return spec;
    }

    return nil;
}

Ptree* Walker::StripCvFromIntegralType(Ptree* integral)
{
    if(integral == nil)
        return nil;

    if(!integral->IsLeaf())
        if(integral->Car()->IsA(CONST, VOLATILE))
            return Ptree::Second(integral);
        else if(Ptree::Second(integral)->IsA(CONST, VOLATILE))
            return integral->Car();

    return integral;
}

Ptree* Walker::TranslateComma(Ptree* exp)
{
    Ptree* left = exp->First();
    Ptree* left2 = Translate(left);
    Ptree* right = exp->Third();
    Ptree* right2 = Translate(right);
    if(left == left2 && right == right2)
        return exp;
    else
        return new PtreeCommaExpr(left2, Ptree::List(exp->Second(), right2));
}

void Walker::TypeofComma(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Third(), t);
}

Ptree* Walker::TranslateAssign(Ptree* exp)
{
    Ptree* left = exp->First();
    Ptree* left2 = Translate(left);
    Ptree* right = exp->Third();
    Ptree* right2 = Translate(right);
    if(left == left2 && right == right2)
        return exp;
    else
        return new PtreeAssignExpr(left2, Ptree::List(exp->Second(), right2));
}

void Walker::TypeofAssign(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->First(), t);
}

Ptree* Walker::TranslateCond(Ptree* exp)
{
    Ptree* c = exp->First();
    Ptree* c2 = Translate(c);
    Ptree* t = exp->Third();
    Ptree* t2 = Translate(t);
    Ptree* e = exp->Nth(4);
    Ptree* e2 = Translate(e);
    if(c == c2 && t == t2 && e == e2)
        return exp;
    else
        return new PtreeCondExpr(c2, Ptree::List(exp->Second(), t2,
                                                 exp->Nth(3), e2));
}

void Walker::TypeofCond(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Third(), t);
}

Ptree* Walker::TranslateInfix(Ptree* exp)
{
    Ptree* left = exp->First();
    Ptree* left2 = Translate(left);
    Ptree* right = exp->Third();
    Ptree* right2 = Translate(right);
    if(left == left2 && right == right2)
        return exp;
    else
        return new PtreeInfixExpr(left2, Ptree::List(exp->Second(), right2));
}

void Walker::TypeofInfix(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->First(), t);
}

Ptree* Walker::TranslatePm(Ptree* exp)
{
    Ptree* left = exp->First();
    Ptree* left2 = Translate(left);
    Ptree* right = exp->Third();
    Ptree* right2 = Translate(right);
    if(left == left2 && right == right2)
        return exp;
    else
        return new PtreePmExpr(left2, Ptree::List(exp->Second(), right2));
}

void Walker::TypeofPm(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Third(), t);
    t.Dereference();
}

Ptree* Walker::TranslateCast(Ptree* exp)
{
    Ptree* e = exp->Nth(3);
    Ptree* e2 = Translate(e);
    if(e == e2)
        return exp;
    else
        return new PtreeCastExpr(exp->First(),
                                 Ptree::ShallowSubst(e2, e, exp->Cdr()));
}

void Walker::TypeofCast(Ptree* exp, TypeInfo& t)
{
    t.Set(exp->Second()->Second()->GetEncodedType(), env);
}

Ptree* Walker::TranslateUnary(Ptree* exp)
{
    Ptree* oprnd = exp->Second();
    Ptree* oprnd2 = Translate(oprnd);
    if(oprnd == oprnd2)
        return exp;
    else
        return new PtreeUnaryExpr(exp->First(), Ptree::List(oprnd2));
}

void Walker::TypeofUnary(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Second(), t);

    Ptree* op = exp->First();
    if(op->Eq('*'))
        t.Dereference();
    else if(op->Eq('&'))
        t.Reference();
}

Ptree* Walker::TranslateThrow(Ptree* exp)
{
    Ptree* oprnd = exp->Second();
    Ptree* oprnd2 = Translate(oprnd);
    if(oprnd == oprnd2)
        return exp;
    else
        return new PtreeThrowExpr(exp->First(), Ptree::List(oprnd2));
}

void Walker::TypeofThrow(Ptree*, TypeInfo& t)
{
    t.SetVoid();
}

Ptree* Walker::TranslateSizeof(Ptree* exp)
{
    Ptree* e = exp->Second();
    if(e->Eq('('))
        e = exp->Third();

    Ptree* e2 = Translate(e);
    if(e == e2)
        return exp;
    else
        return new PtreeSizeofExpr(exp->First(),
                                   Ptree::ShallowSubst(e2, e, exp->Cdr()));
}

void Walker::TypeofSizeof(Ptree*, TypeInfo& t)
{
    t.SetInt();
}

Ptree* Walker::TranslateNew(Ptree* exp)
{
    Ptree *p;
    Ptree *userkey, *scope, *op, *placement, *type, *init;

    p = exp;
    userkey = p->Car();
    if(userkey == nil || !userkey->IsLeaf())
        p = exp->Cdr();         // user keyword
    else
        userkey = nil;

    if(p->Car()->Eq("::")){
        scope = p->Car();
        p = p->Cdr();
    }
    else
        scope = nil;

    op = p->Car();
    placement = p->Cadr();
    type = p->Third();
    init = p->Nth(3);
    return TranslateNew2(exp, userkey, scope, op, placement, type, init);
}

Ptree* Walker::TranslateNew2(Ptree* exp, Ptree*, Ptree*,
                             Ptree*, Ptree* placement,
                             Ptree* type, Ptree* init)
{
    Ptree* placement2 = TranslateArguments(placement);
    Ptree* type2 = TranslateNew3(type);
    Ptree* init2 = TranslateArguments(init);
    if(placement == placement2 && init == init2)
        return exp;
    else
        return new PtreeNewExpr(exp->Car(),
                                Ptree::ShallowSubst(placement2, placement,
                                                    type2, type,
                                                    init2, init,
                                                    exp->Cdr()));
}

Ptree* Walker::TranslateNew3(Ptree* type)
{
    Ptree* p = type;
    if(p->Car()->Eq('('))
        p = p->Second();

    Ptree* decl = p->Second();
    Ptree* decl2 = TranslateNewDeclarator(decl);
    if(decl == decl2)
        return type;
    else
        return Ptree::Subst(decl2, decl, type);
}

void Walker::TypeofNew(Ptree* exp, TypeInfo& t)
{
    Ptree *p, *userkey, *type;

    p = exp;
    userkey = p->Car();
    if(userkey == nil || !userkey->IsLeaf())
        p = exp->Cdr();         // user keyword

    if(p->Car()->Eq("::"))
        p = p->Cdr();

    type = p->Third();

    if(type->Car()->Eq('('))
        t.Set(type->Second()->Second()->GetEncodedType(), env);
    else
        t.Set(type->Second()->GetEncodedType(), env);

    t.Reference();
}

Ptree* Walker::TranslateDelete(Ptree* exp)
{
    Ptree* obj = Ptree::Last(exp)->Car();
    Ptree* obj2 = Translate(obj);
    if(obj == obj2)
        return exp;
    else
        return new PtreeDeleteExpr(exp->Car(),
                                   Ptree::ShallowSubst(obj2, obj,
                                                       exp->Cdr()));
}

void Walker::TypeofDelete(Ptree*, TypeInfo& t)
{
    t.SetVoid();
}

Ptree* Walker::TranslateThis(Ptree* exp)
{
    return exp;
}

void Walker::TypeofThis(Ptree*, TypeInfo& t)
{
    t.Set(env->LookupThis());
}

Ptree* Walker::TranslateVariable(Ptree* exp)
{
    return exp;
}

/*
  This may be a class name if the expression is a function-style cast.
*/
void Walker::TypeofVariable(Ptree* exp, TypeInfo& t)
{
    bool is_type_name;

    if(env->Lookup(exp, is_type_name, t))
        if(is_type_name)        // if exp is a class name
            t.Reference();      // see TypeofFuncall
}

/*
  TranslateFstyleCast() deals with function-style casts
  to an integral type
*/
Ptree* Walker::TranslateFstyleCast(Ptree* exp)
{
    Ptree* args = exp->Cdr();
    Ptree* args2 = TranslateArguments(args);
    if(args == args2)
        return exp;
    else
        return new PtreeFstyleCastExpr(exp->GetEncodedType(), exp->Car(),
                                       args2);
}

void Walker::TypeofFstyleCast(Ptree* exp, TypeInfo& t)
{
    t.Set(exp->GetEncodedType(), env);
}

Ptree* Walker::TranslateArray(Ptree* exp)
{
    Ptree* array = exp->Car();
    Ptree* array2 = Translate(array);
    Ptree* index = exp->Third();
    Ptree* index2 = Translate(index);
    if(array == array2 && index == index2)
        return exp;
    else
        return new PtreeArrayExpr(array2, Ptree::Subst(index2, index,
                                                       exp->Cdr()));
}

void Walker::TypeofArray(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Car(), t);
    t.Dereference();
}

/*
  TranslateFuncall() also deals with function-style casts to a class.
*/
Ptree* Walker::TranslateFuncall(Ptree* exp)
{
    Ptree* fun = exp->Car();
    Ptree* fun2 = Translate(fun);
    Ptree* args = exp->Cdr();
    Ptree* args2 = TranslateArguments(args);
    if(fun == fun2 && args == args2)
        return exp;
    else
        return new PtreeFuncallExpr(fun2, args2);
}

void Walker::TypeofFuncall(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Car(), t);
    if(!t.IsFunction())
        t.Dereference();        // maybe a pointer to a function

    t.Dereference();
}

Ptree* Walker::TranslatePostfix(Ptree* exp)
{
    Ptree* left = exp->Car();
    Ptree* left2 = Translate(left);
    if(left == left2)
        return exp;
    else
        return new PtreePostfixExpr(left2, exp->Cdr());
}

void Walker::TypeofPostfix(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Car(), t);
}

Ptree* Walker::TranslateUserStatement(Ptree* exp)
{
    return exp;
}

void Walker::TypeofUserStatement(Ptree*, TypeInfo& t)
{
    t.Unknown();
}

Ptree* Walker::TranslateDotMember(Ptree* exp)
{
    Ptree* left = exp->Car();
    Ptree* left2 = Translate(left);
    if(left == left2)
        return exp;
    else
        return new PtreeDotMemberExpr(left2, exp->Cdr());
}

void Walker::TypeofDotMember(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Car(), t);
    t.SetMember(exp->Third());
}

Ptree* Walker::TranslateArrowMember(Ptree* exp)
{
    Ptree* left = exp->Car();
    Ptree* left2 = Translate(left);
    if(left == left2)
        return exp;
    else
        return new PtreeArrowMemberExpr(left2, exp->Cdr());
}

void Walker::TypeofArrowMember(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Car(), t);
    t.Dereference();
    t.SetMember(exp->Third());
}

Ptree* Walker::TranslateParen(Ptree* exp)
{
    Ptree* e = exp->Second();
    Ptree* e2 = Translate(e);
    if(e == e2)
        return exp;
    else
        return new PtreeParenExpr(exp->Car(), Ptree::List(e2, exp->Third()));
}

void Walker::TypeofParen(Ptree* exp, TypeInfo& t)
{
    Typeof(exp->Second(), t);
}

Ptree* Walker::TranslateStaticUserStatement(Ptree* exp)
{
    return exp;
}

void Walker::TypeofStaticUserStatement(Ptree*, TypeInfo& t)
{
    t.Unknown();
}

Ptree* Walker::TranslateNewDeclarator(Ptree* decl)
{
    Ptree* decl2 = decl;
    Ptree* p = decl;
    while(p != nil){
        Ptree* head = p->Car();
        if(head == nil)
            return decl;
        else if(head->Eq('[')){
            Ptree* p2 = TranslateNewDeclarator2(p);
            if(p == p2)
                return decl;
            else{
                decl2 = Ptree::ShallowSubst(p2, p, decl);
                break;
            }
        }
        else if(!head->IsLeaf() && head->Car()->Eq('(')){
            Ptree* d = head->Cadr();
            Ptree* d2 = TranslateNewDeclarator(d);
            decl2 = Ptree::ShallowSubst(d2, d, decl);
            break;
        }

        p = p->Cdr();
    }

    if(p == nil)
        return decl;
    else if(decl->IsA(ntDeclarator))
        return new PtreeDeclarator((PtreeDeclarator*)decl,
                                   decl2->Car(), decl2->Cdr());
    else
        return decl2;
}

Ptree* Walker::TranslateNewDeclarator2(Ptree* decl)
{
    for(Ptree* p = decl; p != nil; p = p->Cdr()){
        Ptree* head = p->Car();
        if(head->Eq('[')){
            Ptree* size = p->Cadr();
            Ptree* size2 = Translate(size);
            if(size != size2){
                Ptree* q = TranslateNewDeclarator2(Ptree::ListTail(p, 3));
                return Ptree::Nconc(Ptree::List(p->Car(), size2, p->Third()),
                                    q);
            }
        }
        else if(head->Eq('('))
            break;
    }

    return decl;
}

Ptree* Walker::TranslateArguments(Ptree* arglist)
{
    if(arglist == nil)
        return arglist;

    PtreeArray array;
    bool changed = FALSE;
    Ptree* body = Ptree::Second(arglist);
    Ptree* args = body;
    while(args != nil){
        Ptree* p = args->Car();
        Ptree* q = Translate(p);
        array.Append(q);
        if(p != q)
            changed = TRUE;

        args = args->Cdr();
        if(args != nil){
            array.Append(args->Car());
            args = args->Cdr();
        }
    }

    if(changed)
        return Ptree::ShallowSubst(array.All(), body, arglist);
    else
        return arglist;
}

void Walker::SetDeclaratorComments(Ptree* def, Ptree* comments)
{
    if (def == nil || !def->IsA(ntDeclaration))
        return;

    Ptree* decl;
    int n = 0;
    for (;;) {
        int i = n++;
        decl = NthDeclarator(def, i);
        if (decl == nil)
            break;
        else if (decl->IsA(ntDeclarator))
            ((PtreeDeclarator*)decl)->SetComments(comments);
    }
}

Ptree* Walker::NthDeclarator(Ptree* def, int& nth)
{
    Ptree* decls = def->Third();
    if(decls == nil || decls->IsLeaf())
        return nil;

    if(decls->IsA(ntDeclarator)){       // if it is a function
        if(nth-- == 0)
            return decls;
    }
    else
        while(decls != nil && !decls->IsLeaf()){
            if(nth-- == 0)
                return decls->Car();

            if((decls = decls->Cdr()) != nil)
                decls = decls->Cdr();           // skip ,
        }

    return nil;
}

Ptree* Walker::FindDeclarator(Ptree* def, char* name, int len,
                              char* signature, int& nth, Environment* e)
{
    Ptree* decls = def->Third();
    if(decls == nil || decls->IsLeaf())
        return nil;

    if(decls->IsA(ntDeclarator)){       // if it is a function
        if(MatchedDeclarator(decls, name, len, signature, e))
            return decls;

        ++nth;
    }
    else
        while(decls != nil){
            Ptree* d = decls->Car();
            if(MatchedDeclarator(d, name, len, signature, e))
                return d;

            ++nth;
            if((decls = decls->Cdr()) != nil)
                decls = decls->Cdr();           // skip ,
        }

    return nil;
}

bool Walker::MatchedDeclarator(Ptree* decl, char* name, int len,
                               char* signature, Environment* e)
{
    char* str;
    int strlen;
    char* sig;

    str = decl->GetEncodedName();
    sig = decl->GetEncodedType();
    if(str == nil || sig == nil)
        return FALSE;

    str = Encoding::GetBaseName(str, strlen, e);
    return bool(len == strlen && memcmp(name, str, len) == 0
                && strcmp(signature, sig) == 0);
}

bool Walker::WhichDeclarator(Ptree* def, Ptree* name, int& nth,
                             Environment* env)
{
    char* str;
    int len;
    Environment* e;
    Ptree* decls = def->Third();
    if(decls == nil || decls->IsLeaf())
        return FALSE;

    if(decls->IsA(ntDeclarator)){       // if it is a function
        str = decls->GetEncodedName();
        e = env;
        str = Encoding::GetBaseName(str, len, e);
        if(name->Eq(str, len))
            return TRUE;

        ++nth;
    }
    else
        while(decls != nil){
            str = decls->Car()->GetEncodedName();
            e = env;
            str = Encoding::GetBaseName(str, len, e);
            if(name->Eq(str, len))
                return TRUE;

            ++nth;
            if((decls = decls->Cdr()) != nil)
                decls = decls->Cdr();
        }

    return FALSE;
}

void Walker::ErrorMessage(char* msg, Ptree* name, Ptree* where)
{
    parser->ErrorMessage(msg, name, where);
}

void Walker::WarningMessage(char* msg, Ptree* name, Ptree* where)
{
    parser->WarningMessage(msg, name, where);
}

// InaccurateErrorMessage() may report a wrong line number.

void Walker::InaccurateErrorMessage(char* msg, Ptree* name, Ptree* where)
{
    if(default_parser == nil)
        MopErrorMessage("Walker::InaccurateErrorMessage()",
                        "no default parser");
    else
        default_parser->ErrorMessage(msg, name, where);
}

void Walker::InaccurateWarningMessage(char* msg, Ptree* name, Ptree* where)
{
    if(default_parser == nil)
        MopErrorMessage("Walker::InaccurateWarningMessage()",
                        "no default parser");
    else
        default_parser->WarningMessage(msg, name, where);
}

---