1| /*
    2|   Copyright (C) 1997-2000 Shigeru Chiba, University of Tsukuba.
    3| 
    4|   Permission to use, copy, distribute and modify this software and   
    5|   its documentation for any purpose is hereby granted without fee,        
    6|   provided that the above copyright notice appear in all copies and that 
    7|   both that copyright notice and this permission notice appear in 
    8|   supporting documentation.
    9| 
   10|   Shigeru Chiba makes no representations about the suitability of this 
   11|   software for any purpose.  It is provided "as is" without express or
   12|   implied warranty.
   13| */
   14| 
   15| /*
   16|   This encoding is also interpreted by TypeInfo.  If you modify this
   17|   file, check typeinfo.{h,cc} out as well.
   18| 
   19|   'b' boolean
   20|   'c' char
   21|   'i' int (signed, unsigned)
   22|   's' short (short int)
   23|   'l' long (long int)
   24|   'j' long long
   25|   'f' float
   26|   'd' double
   27|   'r' long double
   28|   'v' void
   29| 
   30|   'T' template class (e.g. Foo<int,char> ==> T[3]Foo[2]ic.  [2] means
   31|       the length of "ic".  It doesn't mean the number of template
   32|       arguments.
   33|   'e' ...
   34|   '?' no return type.  the return type of constructors
   35|   '*' non-type template parameter
   36| 
   37|   'S' singned
   38|   'U' unsigned
   39|   'C' const
   40|   'V' volatile
   41| 
   42|   'P' pointer
   43|   'R' reference
   44|   'A' []
   45|   'F' function (e.g. char foo(int) ==> Fi_c)
   46|   'M' pointer to member (e.g. Type::* ==> M[4]Type)
   47| 
   48|   'Q' qualified class (e.g. X::YY ==> Q[2][1]X[2]YY, ::YY ==> Q[2][0][2]YY)
   49| 
   50|   [x] means (0x80 + x)
   51|   '0' means :: (global scope)
   52| 
   53|   Special function names:
   54| 
   55|   operator + ==> +
   56|   operator new[] ==> new[]
   57|   operator <type> ==> @<encoded type>          cas
   58| */
   59| 
   60| #include <cstring>
   61| #include <iostream>
   62| #include "encoding.h"
   63| #include "token.h"
   64| #include "ptree.h"
   65| #include "env.h"
   66| #include "mop.h"
   67| #include "typeinfo.h"
   68| 
   69| Ptree* Encoding::bool_t = nil;
   70| Ptree* Encoding::char_t = nil;
   71| Ptree* Encoding::int_t = nil;
   72| Ptree* Encoding::short_t = nil;
   73| Ptree* Encoding::long_t = nil;
   74| Ptree* Encoding::float_t = nil;
   75| Ptree* Encoding::double_t = nil;
   76| Ptree* Encoding::void_t = nil;
   77| 
   78| Ptree* Encoding::signed_t = nil;
   79| Ptree* Encoding::unsigned_t = nil;
   80| Ptree* Encoding::const_t = nil;
   81| Ptree* Encoding::volatile_t = nil;
   82| 
   83| Ptree* Encoding::operator_name = nil;
   84| Ptree* Encoding::new_operator = nil;
   85| Ptree* Encoding::anew_operator = nil;
   86| Ptree* Encoding::delete_operator = nil;
   87| Ptree* Encoding::adelete_operator = nil;
   88| 
   89| Ptree* Encoding::star = nil;
   90| Ptree* Encoding::ampersand = nil;
   91| Ptree* Encoding::comma = nil;
   92| Ptree* Encoding::dots = nil;
   93| Ptree* Encoding::scope = nil;
   94| Ptree* Encoding::tilder = nil;
   95| Ptree* Encoding::left_paren = nil;
   96| Ptree* Encoding::right_paren = nil;
   97| Ptree* Encoding::left_bracket = nil;
   98| Ptree* Encoding::right_bracket = nil;
   99| Ptree* Encoding::left_angle = nil;
  100| Ptree* Encoding::right_angle = nil;
  101| 
  102| const int DigitOffset = 0x80;
  103| 
  104| void Encoding::do_init_static()
  105| {
  106|     Encoding::bool_t = new LeafBOOLEAN("bool", 4);
  107|     Encoding::char_t = new LeafCHAR("char", 4);
  108|     Encoding::int_t = new LeafINT("int", 3);
  109|     Encoding::short_t = new LeafSHORT("short", 5);
  110|     Encoding::long_t = new LeafLONG("long", 4);
  111|     Encoding::float_t = new LeafFLOAT("float", 5);
  112|     Encoding::double_t = new LeafDOUBLE("double", 6);
  113|     Encoding::void_t = new LeafVOID("void", 4);
  114| 
  115|     Encoding::signed_t = new LeafSIGNED("signed", 6);
  116|     Encoding::unsigned_t = new LeafUNSIGNED("unsigned", 8);
  117|     Encoding::const_t = new LeafCONST("const", 5);
  118|     Encoding::volatile_t = new LeafVOLATILE("volatile", 8);
  119| 
  120|     Encoding::operator_name = new LeafReserved("operator", 8);
  121|     Encoding::new_operator = new LeafReserved("new", 3);
  122|     Encoding::anew_operator = new LeafReserved("new[]", 5);
  123|     Encoding::delete_operator = new LeafReserved("delete", 6);
  124|     Encoding::adelete_operator = new LeafReserved("delete[]", 8);
  125| 
  126|     Encoding::star = new Leaf("*", 1);
  127|     Encoding::ampersand = new Leaf("&", 1);
  128|     Encoding::comma = new Leaf(",", 1);
  129|     Encoding::dots = new Leaf("...", 3);
  130|     Encoding::scope = new Leaf("::", 2);
  131|     Encoding::tilder = new Leaf("~", 1);
  132|     Encoding::left_paren = new Leaf("(", 1);
  133|     Encoding::right_paren = new Leaf(")", 1);
  134|     Encoding::left_bracket = new Leaf("[", 1);
  135|     Encoding::right_bracket = new Leaf("]", 1);
  136|     Encoding::left_angle = new Leaf("<", 1);
  137|     Encoding::right_angle = new Leaf(">", 1);
  138| 
  139| }
  140| 
  141| void Encoding::Reset(Encoding& e)
  142| {
  143|     len = e.len;
  144|     if(len > 0)
  145|         memmove(name, e.name, len);
  146| }
  147| 
  148| char* Encoding::Get()
  149| {
  150|     if(len == 0)
  151|         return nil;
  152|     else{
  153|         char* s = new (GC) char[len + 1];
  154|         memmove(s, name, len);
  155|         s[len] = '\0';
  156|         return s;
  157|     }
  158| }
  159| 
  160| void Encoding::Print(std::ostream& s, char* p)
  161| {
  162|     unsigned char* ptr = (unsigned char*)p;
  163|     for(;*ptr != '\0'; ++ptr)
  164|         if(*ptr < 0x80)
  165|             s << char(*ptr);
  166|         else
  167|             s << char(*ptr - 0x80 + '0');
  168| }
  169| 
  170| // GetBaseName() returns "Foo" if ENCODE is "Q[2][1]X[3]Foo", for example.
  171| // If an error occurs, the function returns nil.
  172| 
  173| char* Encoding::GetBaseName(char* encode, int& len, Environment*& env)
  174| {
  175|     if(encode == nil){
  176|         len = 0;
  177|         return nil;
  178|     }
  179| 
  180|     Environment* e = env;
  181|     unsigned char* p = (unsigned char*)encode;
  182|     if(*p == 'Q'){
  183|         int n = p[1] - 0x80;
  184|         p += 2;
  185|         while(n-- > 1){
  186|             int m = *p++;
  187|             if(m == 'T')
  188|                m = GetBaseNameIfTemplate(p, e);
  189|             else if(m < 0x80){        /
  190|                len = 0;
  191|                return nil;
  192|         }
  193|             else{                    
  194|                m -= 0x80;
  195|                if(m <= 0){          // if global scope (e
  196|                 if(e != nil)
  197|                       e = e->GetBottom();
  198|         }
  199|         else
  200|                    e = ResolveTypedefName(e, (char*)p, m);
  201|         }
  202| 
  203|            p += m;
  204|         }
  205| 
  206|         env = e;
  207|     }
  208| 
  209|     if(*p == 'T'){             // t
  210|         int m = p[1] - 0x80;
  211|         int n = p[m + 2] - 0x80;
  212|         len = m + n + 3;
  213|         return (char*)p;
  214|     }
  215|     else if(*p < 0x80){        /
  216|         len = 0;
  217|         return nil;
  218|     }
  219|     else{
  220|         len = *p - 0x80;
  221|         return (char*)p + 1;
  222|     }
  223| }
  224| 
  225| Environment* Encoding::ResolveTypedefName(Environment* env,
  226|                              char* name, int len)
  227| {
  228|     TypeInfo tinfo;
  229|     Bind* bind;
  230|     Class* c = nil;
  231| 
  232|     if(env != nil)
  233|         if (env->LookupType(name, len, bind) && bind != nil)
  234|             switch(bind->What()){
  235|             case Bind::isClassName :
  236|                c = bind->ClassMetaobject();
  237|         break;
  238|             case Bind::isTypedefName :
  239|                bind->GetType(tinfo, env);
  240|                c = tinfo.ClassMetaobject();
  241|                /* if (c == nil) */
  242|                env = nil;
  243|         break;
  244|             default :
  245|         break;
  246|         }
  247|         else if (env->LookupNamespace(name, len)) {
  248|             /* For the time being, we simply ignore name spaces.
  249|              * For example, std::T is identical to ::T.
  250|         */
  251|             env = env->GetBottom();
  252|         }
  253|         else
  254|             env = nil;        // unknown type
  255| 
  256|     if(c != nil)
  257|         return c->GetEnvironment();
  258|     else
  259|         return env;
  260| }
  261| 
  262| int Encoding::GetBaseNameIfTemplate(unsigned char* name, Environment*& e)
  263| {
  264|     int m = name[0] - 0x80;
  265|     if(m <= 0)
  266|         return name[1] - 0x80 + 2;
  267| 
  268|     Bind* b;
  269|     if(e != nil && e->LookupType((char*)&name[1], m, b))
  270|         if(b != nil && b->What() == Bind::isTemplateClass){
  271|             Class* c = b->ClassMetaobject();
  272|             if(c != nil){
  273|                e = c->GetEnvironment();
  274|                return m + (name[m + 1] - 0x80) + 2;
  275|         }
  276|         }
  277| 
  278|     // the template name was not found.
  279|     e = nil;
  280|     return m + (name[m + 1] - 0x80) + 2;
  281| }
  282| 
  283| unsigned char* Encoding::GetTemplateArguments(unsigned char* name, int& len)
  284| {
  285|     int m = name[0] - 0x80;
  286|     if(m <= 0){
  287|         len = name[1] - 0x80;
  288|         return &name[2];
  289|     }
  290|     else{
  291|         len = name[m + 1] - 0x80;
  292|         return &name[m + 2];
  293|     }
  294| }
  295| 
  296| void Encoding::CvQualify(Ptree* cv1, Ptree* cv2)
  297| {
  298|     bool c = FALSE, v = FALSE;
  299|     if(cv1 != nil && !cv1->IsLeaf())
  300|         while(cv1 != nil){
  301|             int kind = cv1->Car()->What();
  302|             cv1 = cv1->Cdr();
  303|             if(kind == CONST)
  304|                c = TRUE;
  305|             else if(kind == VOLATILE)
  306|                v = TRUE;
  307|         }
  308| 
  309|     if(cv2 != nil && !cv2->IsLeaf())
  310|         while(cv2 != nil){
  311|             int kind = cv2->Car()->What();
  312|             cv2 = cv2->Cdr();
  313|             if(kind == CONST)
  314|                c = TRUE;
  315|             else if(kind == VOLATILE)
  316|                v = TRUE;
  317|         }
  318| 
  319|     if(v)
  320|         Insert('V');
  321| 
  322|     if(c)
  323|         Insert('C');
  324| }
  325| 
  326| void Encoding::GlobalScope()
  327| {
  328|     Append(DigitOffset);
  329| }
  330| 
  331| // SimpleName() is also used for operator names
  332| 
  333| void Encoding::SimpleName(Ptree* id)
  334| {
  335|     AppendWithLen(id->GetPosition(), id->GetLength());
  336| }
  337| 
  338| // NoName() generates a internal name for no-name enum and class
  339| // declarations.
  340| 
  341| void Encoding::NoName()
  342| {
  343|     static int i = 0;
  344|     static unsigned char name[] = "`0000";
  345|     int n = i++;
  346|     name[1] = n / 1000 + '0';
  347|     name[2] = (n / 100) % 10 + '0';
  348|     name[3] = (n / 10) % 10 + '0';
  349|     name[4] = n % 10 + '0';
  350|     AppendWithLen((char*)name, 5);
  351| }
  352| 
  353| void Encoding::Template(Ptree* name, Encoding& args)
  354| {
  355|     Append('T');
  356|     SimpleName(name);
  357|     AppendWithLen(args);
  358| }
  359| 
  360| void Encoding::Qualified(int n)
  361| {
  362|     if(len + 1 >= MaxNameLen)
  363|         MopErrorMessage("Encoding::Qualified()",
  364|                       "too long encoded name");
  365| 
  366|     memmove(name + 2, name, len);
  367|     len += 2;
  368|     name[0] = 'Q';
  369|     name[1] = (unsigned char)(DigitOffset + n);
  370| }
  371| 
  372| void Encoding::Destructor(Ptree* class_name)
  373| {
  374|     int len = class_name->GetLength();
  375|     Append((unsigned char)(DigitOffset + len + 1));
  376|     Append('~');
  377|     Append(class_name->GetPosition(), len);
  378| }
  379| 
  380| void Encoding::PtrOperator(int t)
  381| {
  382|     if(t == '*')
  383|         Insert('P');
  384|     else
  385|         Insert('R');
  386| }
  387| 
  388| void Encoding::PtrToMember(Encoding& encode, int n)
  389| {
  390|     if(n < 2)
  391|         Insert((char*)encode.name, encode.len);
  392|     else{
  393|         Insert((char*)encode.name, encode.len);
  394|         Insert((unsigned char)(DigitOffset + n));
  395|         Insert('Q');
  396|     }
  397| 
  398|     Insert('M');
  399| }
  400| 
  401| void Encoding::CastOperator(Encoding& type)
  402| {
  403|     Append((unsigned char)(DigitOffset + type.len + 1));
  404|     Append('@');
  405|     Append((char*)type.name, type.len);
  406| }
  407| 
  408| void Encoding::Insert(unsigned char c)
  409| {
  410|     if(len >= MaxNameLen)
  411|         MopErrorMessage("Encoding::Insert()",
  412|                       "too long encoded name");
  413| 
  414|     if(len > 0)
  415|         memmove(name + 1, name, len);
  416| 
  417|     ++len;
  418|     name[0] = c;
  419| }
  420| 
  421| void Encoding::Insert(char* str, int n)
  422| {
  423|     if(len + n >= MaxNameLen)
  424|         MopErrorMessage("Encoding::Insert()",
  425|                       "too long encoded name");
  426| 
  427|     if(len > 0)
  428|         memmove(&name[n], name, len);
  429| 
  430|     memmove(name, str, n);
  431|     len += n;
  432| }
  433| 
  434| void Encoding::Append(unsigned char c)
  435| {
  436|     if(len >= MaxNameLen)
  437|         MopErrorMessage("Encoding::Append()",
  438|                       "too long encoded name");
  439| 
  440|     name[len++] = c;
  441| }
  442| 
  443| void Encoding::Append(char* str, int n)
  444| {
  445|     if(len + n >= MaxNameLen)
  446|         MopErrorMessage("Encoding::Append(char*,int)",
  447|                       "too long encoded name");
  448| 
  449|     memmove(&name[len], str, n);
  450|     len += n;
  451| }
  452| 
  453| void Encoding::AppendWithLen(char* str, int n)
  454| {
  455|     if(len + n + 1 >= MaxNameLen)
  456|         MopErrorMessage("Encoding::AppendWithLen()",
  457|                       "too long encoded name");
  458| 
  459|     name[len++] = (unsigned char)(DigitOffset + n);
  460|     memmove(&name[len], str, n);
  461|     len += n;
  462| }
  463| 
  464| Ptree* Encoding::MakePtree(unsigned char*& encoded, Ptree* decl)
  465| {
  466|     Ptree* cv;
  467|     Ptree* typespec = nil;
  468|     if(decl != nil)
  469|         decl = Ptree::List(decl);
  470| 
  471|     for(;;){
  472|         cv = nil;
  473|         switch(*encoded++){
  474|         case 'b' :
  475|             typespec = Ptree::Snoc(typespec, bool_t);
  476|             goto finish;
  477|         case 'c' :
  478|             typespec = Ptree::Snoc(typespec, char_t);
  479|             goto finish;
  480|         case 'i' :
  481|             typespec = Ptree::Snoc(typespec, int_t);
  482|             goto finish;
  483|         case 's' :
  484|             typespec = Ptree::Snoc(typespec, short_t);
  485|             goto finish;
  486|         case 'l' :
  487|             typespec = Ptree::Snoc(typespec, long_t);
  488|             goto finish;
  489|           break;
  490|         case 'j' :
  491|             typespec = Ptree::Nconc(typespec, Ptree::List(long_t, long_t));
  492|             goto finish;
  493|           break;
  494|         case 'f' :
  495|             typespec = Ptree::Snoc(typespec, float_t);
  496|             goto finish;
  497|           break;
  498|         case 'd' :
  499|             typespec = Ptree::Snoc(typespec, double_t);
  500|             goto finish;
  501|           break;
  502|         case 'r' :
  503|             typespec = Ptree::Nconc(typespec, Ptree::List(long_t, double_t));
  504|             goto finish;
  505|         case 'v' :
  506|             typespec = Ptree::Snoc(typespec, void_t);
  507|             goto finish;
  508|         case 'e' :
  509|             return dots;
  510|         case '?' :
  511|             goto finish;
  512|         case 'Q' :
  513|             typespec = Ptree::Snoc(typespec, MakeQname(encoded));
  514|             goto finish;
  515|         case 'S' :
  516|             typespec = Ptree::Snoc(typespec, signed_t);
  517|           break;
  518|         case 'U' :
  519|             typespec = Ptree::Snoc(typespec, unsigned_t);
  520|           break;
  521|         case 'C' :
  522|             if(*encoded == 'V'){
  523|                ++encoded;
  524|                cv = Ptree::List(const_t, volatile_t);
  525|         }
  526|         else
  527|                cv = Ptree::List(const_t);
  528| 
  529|             goto const_or_volatile;
  530|         case 'V' :
  531|             cv = Ptree::List(volatile_t);
  532|         const_or_volatile :
  533|             switch(*encoded) {
  534|             case 'M' :
  535|             case 'P' :
  536|             case 'R' :
  537|                decl = Ptree::Nconc(cv, decl);
  538|         break;
  539|             case 'F' :
  540|                ++encoded;
  541|                goto cv_function;
  542|             default :
  543|                typespec = Ptree::Nconc(cv, typespec);
  544|         break;
  545|         }
  546|           break;
  547|         case 'M' :
  548|         {
  549|                Ptree* ptr;
  550|                if(*encoded == 'Q')
  551|                    ptr = MakeQname(++encoded);
  552|         else
  553|                    ptr = MakeLeaf(encoded);
  554| 
  555|                ptr = Ptree::List(ptr, scope, star);
  556|                decl = Ptree::Cons(ptr, decl);
  557|         }
  558| 
  559|             goto pointer_or_reference;
  560|         case 'P' :
  561|             decl = Ptree::Cons(star, decl);
  562|             goto pointer_or_reference;
  563|         case 'R' :
  564|             decl = Ptree::Cons(ampersand, decl);
  565|         pointer_or_reference :
  566|             if(*encoded == 'A' || *encoded == 'F')
  567|                decl = Ptree::List(Ptree::List(left_paren, decl,
  568|                              right_paren));
  569| 
  570|           break;
  571|         case 'A' :
  572|             decl = Ptree::Nconc(decl, Ptree::List(left_bracket,
  573|                       right_bracket));
  574|           break;
  575|         case 'F' :
  576|         cv_function :
  577|         {
  578|                Ptree* args = nil;
  579|                while(*encoded != '\0'){
  580|                    if(*encoded == '_'){
  581|                ++encoded;
  582|         break;
  583|         }
  584|                    else if(*encoded == 'v'){
  585|                encoded += 2;
  586|         break;
  587|         }
  588| 
  589|                    if(args != nil)
  590|                       args = Ptree::Snoc(args, comma);
  591| 
  592|                    args = Ptree::Snoc(args, MakePtree(encoded, nil));
  593|         }
  594| 
  595|                decl = Ptree::Nconc(decl, Ptree::List(left_paren, args,
  596|                              right_paren));
  597|                if(cv != nil)
  598|                    decl = Ptree::Nconc(decl, cv);
  599|         }
  600|           break;
  601|         case '\0' :
  602|             goto finish;
  603|         case 'T' :
  604|         {
  605|                Ptree* tlabel = MakeLeaf(encoded);      
  606|                Ptree* args = nil;
  607|                int n = *encoded++ - DigitOffset;
  608|                unsigned char* stop = encoded + n;
  609|                while(encoded < stop){
  610|                    if(args != nil)
  611|                       args = Ptree::Snoc(args, comma);
  612| 
  613|                    args = Ptree::Snoc(args, MakePtree(encoded, nil));
  614|         }
  615| 
  616|                tlabel = Ptree::List(tlabel,
  617|                              Ptree::List(left_angle, args, right_angle));
  618|                typespec = Ptree::Nconc(typespec, tlabel);
  619|                goto finish;
  620|         }
  621|         case '*' :
  622|             goto error;
  623|         default :
  624|             if(*--encoded >= DigitOffset){
  625|                if(typespec == nil)
  626|                    typespec = MakeLeaf(encoded);
  627|         else
  628|                    typespec = Ptree::Snoc(typespec, MakeLeaf(encoded));
  629| 
  630|                goto finish;
  631|         }
  632|         error :
  633|             MopErrorMessage("TypeInfo::MakePtree()",
  634|                           "sorry, cannot handle this type");
  635|           break;
  636|         }
  637|     }
  638| 
  639| finish :
  640|     return Ptree::List(typespec, decl);
  641| }
  642| 
  643| Ptree* Encoding::MakeQname(unsigned char*& encoded)
  644| {
  645|     int n = *encoded++ - DigitOffset;
  646|     Ptree* qname = nil;
  647|     while(n-- > 0){
  648|         Ptree* leaf = MakeLeaf(encoded);
  649|         if(leaf != nil)
  650|             qname = Ptree::Snoc(qname, leaf);
  651| 
  652|         if(n > 0)
  653|             qname = Ptree::Snoc(qname, scope);
  654|     }
  655| 
  656|     return qname;
  657| }
  658| 
  659| Ptree* Encoding::MakeLeaf(unsigned char*& encoded)
  660| {
  661|     Ptree* leaf;
  662|     int len = *encoded++ - DigitOffset;
  663|     if(len > 0)
  664|         leaf = new Leaf((char*)encoded, len);
  665|     else
  666|         leaf = nil;
  667| 
  668|     encoded += len;
  669|     return leaf;
  670| }
  671| 
  672| bool Encoding::IsSimpleName(unsigned char* p)
  673| {
  674|     return *p >= DigitOffset;
  675| }
  676| 
  677| Ptree* Encoding::NameToPtree(char* name, int len)
  678| {
  679|     if(name == nil)
  680|         return nil;
  681| 
  682|     if(name[0] == 'n'){
  683|         if(len == 5 && strncmp(name, "new[]", 5) == 0)
  684|             return Ptree::List(operator_name, anew_operator);
  685|         else if(len == 3 && strncmp(name, "new", 3) == 0)
  686|             return Ptree::List(operator_name, new_operator);
  687|     }
  688|     else if(name[0] == 'd'){
  689|         if(len == 8 && strncmp(name, "delete[]", 8) == 0)
  690|             return Ptree::List(operator_name, adelete_operator);
  691|         else if(len == 6 && strncmp(name, "delete", 6) == 0)
  692|             return Ptree::List(operator_name, delete_operator);
  693|     }
  694|     else if(name[0] == '~')
  695|         return Ptree::List(tilder, new Leaf(&name[1], len - 1));
  696|     else if(name[0] == '@'){           // ca
  697|         unsigned char* encoded = (unsigned char*)&name[1];
  698|         return Ptree::List(operator_name, MakePtree(encoded, nil));
  699|     }
  700| 
  701|     if(is_letter(name[0]))
  702|         return new Leaf(name, len);
  703|     else
  704|         return Ptree::List(operator_name, new Leaf(name, len));
  705| }
  706|