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|   Copyright (c) 1995, 1996 Xerox Corporation.
   16|   All Rights Reserved.
   17| 
   18|   Use and copying of this software and preparation of derivative works
   19|   based upon this software are permitted. Any copy of this software or
   20|   of any derivative work must include the above copyright notice of
   21|   Xerox Corporation, this paragraph and the one after it.  Any
   22|   distribution of this software or derivative works must comply with all
   23|   applicable United States export control laws.
   24| 
   25|   This software is made available AS IS, and XEROX CORPORATION DISCLAIMS
   26|   ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE
   27|   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   28|   PURPOSE, AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED HEREIN, ANY
   29|   LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
   30|   EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
   31|   NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED
   32|   OF THE POSSIBILITY OF SUCH DAMAGES.
   33| */
   34| 
   35| #include <cstdio>
   36| #include <cstring>
   37| #include <cstdarg>
   38| #if !defined(_MSC_VER)
   39| #include <sys/time.h>
   40| #endif
   41| #include "ptree.h"
   42| #include "token.h"
   43| #include "mop.h"
   44| 
   45| #if (defined(sun) && defined(SUNOS4)) || defined(SUNOS5)
   46| extern "C" {
   47|     int gettimeofday(struct timeval*, void*);
   48| };
   49| #endif
   50| 
   51| const int MAX = 32;
   52| 
   53| static Ptree** resultsArgs[MAX];
   54| static int resultsIndex;
   55| 
   56| static int CountArgs(char* pat);
   57| static char* SkipSpaces(char* pat);
   58| 
   59| bool Ptree::Match(Ptree* list, char* pattern, ...)
   60| {
   61|     va_list args;
   62|     int n = CountArgs(pattern);
   63|     if(n >= MAX)
   64|         MopErrorMessage("Ptree::Match()", "bomb! too many arguments");
   65| 
   66|     va_start(args, pattern);
   67|     for(int i = 0; i < n; ++i)
   68|         resultsArgs[i] = va_arg(args, Ptree**);
   69| 
   70|     va_end(args);
   71| 
   72|     char* pat = pattern;
   73|     resultsIndex = 0;
   74|     pat = SkipSpaces(pat);
   75|     pat = MatchPat(list, pat);
   76|     if(pat == nil)
   77|         return FALSE;
   78|     else{
   79|         pat = SkipSpaces(pat);
   80|         if(*pat == '\0')
   81|             return TRUE;
   82|         else{
   83|             MopWarningMessage("Ptree::Match()", "[ ] are forgot?");
   84|             MopMoreWarningMessage(pattern);
   85|             return FALSE;
   86|         }
   87|     }
   88| }
   89| 
   90| static int CountArgs(char* pat)
   91| {
   92|     int n = 0;
   93| 
   94|     for(char c = *pat; c != '\0'; c = *++pat)
   95|         if(c == '%'){
   96|             c = *++pat;
   97|             if(c == '?' || c == 'r')
   98|         ++n;
   99|         }
  100| 
  101|     return n;
  102| }
  103| 
  104| char* Ptree::MatchPat(Ptree* list, char* pat)
  105| {
  106|     switch(*pat){
  107|     case '[' :         /* [] mea
  108|         if(list != nil && list->IsLeaf())
  109|             return nil;
  110|         else
  111|             return MatchList(list, pat + 1);
  112|     case '%' :
  113|         switch(pat[1]){
  114|         case '?' :
  115|             *resultsArgs[resultsIndex++] = list;
  116|             return(pat + 2);
  117|         case '*' :
  118|             return(pat + 2);
  119|         case '_' :
  120|         case 'r' :     /* %_ and %r must be appear in a li
  121|             return nil;
  122|         default :
  123|           break;
  124|         }
  125|     }
  126| 
  127|     if(list != nil && list->IsLeaf())
  128|         return MatchWord(list, pat);
  129|     else
  130|         return nil;
  131| }
  132| 
  133| char* Ptree::MatchList(Ptree* list, char* pat)
  134| {
  135|     char c, d;
  136|     pat = SkipSpaces(pat);
  137|     while((c = *pat) != '\0'){
  138|         if(c == ']')
  139|             if(list == nil)
  140|                return(pat + 1);
  141|         else
  142|                return nil;
  143|         else if(c == '%' && (d = pat[1], (d == 'r' || d == '_'))){
  144|             /* %r or %_ */
  145|             if(d == 'r') 
  146|                *resultsArgs[resultsIndex++] = list;
  147| 
  148|             list = nil;
  149|             pat = pat + 2;
  150|         }
  151|         else if(list == nil)
  152|             return nil;
  153|         else{
  154|             pat = MatchPat(list->Car(), pat);
  155|             if(pat == nil)
  156|                return nil;
  157| 
  158|             list = list->Cdr();
  159|         }
  160| 
  161|         pat = SkipSpaces(pat);
  162|     }
  163| 
  164|     MopErrorMessage("Ptree::Match()", "unmatched bracket");
  165|     return nil;
  166| }
  167| 
  168| char* Ptree::MatchWord(Ptree* list, char* pat)
  169| {
  170|     char* str = list->GetPosition();
  171|     int str_len = list->GetLength();
  172| 
  173|     for(int j = 0; ; ++pat){
  174|         char c = *pat;
  175|         switch(c){
  176|         case '\0' :
  177|         case ' ' :
  178|         case '\t' :
  179|         case '[' :
  180|         case ']' :
  181|             if(j == str_len)
  182|                return pat;
  183|         else
  184|                return nil;
  185|         case '%' :
  186|             c = *++pat;
  187|             switch(c){
  188|             case '[' :
  189|             case ']' :
  190|             case '%' :
  191|                if(j >= str_len || c != str[j++])
  192|                return nil;
  193| 
  194|         break;
  195|             default :
  196|                if(j == str_len)
  197|                return pat;
  198|         else
  199|                return nil;
  200|         }
  201|           break;
  202|         default :
  203|             if(j >= str_len || c != str[j++])
  204|                return nil;
  205|         }
  206|     }
  207| }
  208| 
  209| static char* SkipSpaces(char* pat)
  210| {
  211|     while(*pat == ' ' || *pat == '\t')
  212|         ++pat;
  213| 
  214|     return pat;
  215| }
  216| 
  217| Ptree* Ptree::GenSym()
  218| {
  219| #if !defined(_MSC_VER)
  220|     struct timeval time;
  221| #endif
  222|     static char head[] = "_sym";
  223|     static int seed = 1;
  224|     int len1, len2;
  225| 
  226|     IntegerToString(seed, len1);
  227| 
  228| #if !defined(_MSC_VER)
  229|     gettimeofday(&time, NULL);
  230|     uint rnum = (time.tv_sec * 10 + time.tv_usec / 100) & 0xffff;
  231| #else
  232|     static uint time = 0;
  233|     time++;
  234|     uint rnum = time & 0xffff;
  235| #endif
  236|     char* num = IntegerToString(rnum, len2);
  237| 
  238|     int size = len1 + len2 + sizeof(head) - 1 + 1;
  239|     char* name = new (GC) char[size];
  240|     memmove(name, head, sizeof(head) - 1);
  241|     memmove(&name[sizeof(head) - 1], num, len2);
  242|     name[sizeof(head) - 1 + len2] = '_';
  243|     num = IntegerToString(seed++, len1);
  244|     memmove(&name[sizeof(head) - 1 + len2 + 1], num, len1);
  245|     return new Leaf(name, size);
  246| }
  247| 
  248| // If you edit Make(), you should also edit MakeStatement().
  249| 
  250| Ptree* Ptree::Make(const char* pat, ...)
  251| {
  252|     va_list args;
  253|     const int N = 4096;
  254|     static char buf[N];
  255|     char c;
  256|     int len;
  257|     char* ptr;
  258|     Ptree* p;
  259|     Ptree* q;
  260|     int i = 0, j = 0;
  261|     Ptree* result = nil;
  262| 
  263|     va_start(args, pat);
  264|     while((c = pat[i++]) != '\0')
  265|         if(c == '%'){
  266|             c = pat[i++];
  267|             if(c == '%')
  268|                buf[j++] = c;
  269|             else if(c == 'd'){
  270|                ptr = IntegerToString(va_arg(args, int), len);
  271|                memmove(&buf[j], ptr, len);
  272|                j += len;
  273|         }
  274|             else if(c == 's'){
  275|                ptr = va_arg(args, char*);
  276|                len = strlen(ptr);
  277|                memmove(&buf[j], ptr, len);
  278|                j += len;
  279|         }
  280|             else if(c == 'c')
  281|                buf[j++] = va_arg(args, int);
  282|             else if(c == 'p'){
  283|                p = va_arg(args, Ptree*);
  284|                if(p == nil)
  285|                  /* ignore */;
  286|                else if(p->IsLeaf()){
  287|                    memmove(&buf[j], p->GetPosition(), p->GetLength());
  288|                    j += p->GetLength();
  289|         }
  290|                else{   
  291|                if(j > 0)
  292|                       q = List(new DupLeaf(buf, j), p);
  293|                else
  294|                q = List(p);
  295| 
  296|                j = 0;
  297|                    result = Nconc(result, q);
  298|         }
  299|         }
  300|         else
  301|                MopErrorMessage("Ptree::Make()", "invalid format");
  302|         }
  303|         else
  304|             buf[j++] = c;
  305| 
  306|     va_end(args);
  307| 
  308|     if(j > 0)
  309|         if(result == nil)
  310|             result = new DupLeaf(buf, j);
  311|         else
  312|             result = Snoc(result, new DupLeaf(buf, j));
  313| 
  314|     return result;
  315| }
  316| 
  317| /*
  318|   MakeStatement() is identical to Make() except that the generated
  319|   code is wrapped by a PtreeNonExpr object.
  320|   This helps code-traverse functions such as WalkExpr() distinguish
  321|   statements from expressions.
  322| 
  323|   Note: this version is perfectly identical to Make(). 97/3/26
  324| */
  325| Ptree* Ptree::MakeStatement(const char* pat, ...)
  326| {
  327|     va_list args;
  328|     const int N = 4096;
  329|     static char buf[N];
  330|     char c;
  331|     int len;
  332|     char* ptr;
  333|     Ptree* p;
  334|     Ptree* q;
  335|     int i = 0, j = 0;
  336|     Ptree* result = nil;
  337| 
  338|     va_start(args, pat);
  339| 
  340|     Class::WarnObsoleteness("Ptree::MakeStatement()", "Ptree::Make()");
  341| 
  342|     while((c = pat[i++]) != '\0')
  343|         if(c == '%'){
  344|             c = pat[i++];
  345|             if(c == '%')
  346|                buf[j++] = c;
  347|             else if(c == 'd'){
  348|                ptr = IntegerToString(va_arg(args, int), len);
  349|                memmove(&buf[j], ptr, len);
  350|                j += len;
  351|         }
  352|             else if(c == 's'){
  353|                ptr = va_arg(args, char*);
  354|                len = strlen(ptr);
  355|                memmove(&buf[j], ptr, len);
  356|                j += len;
  357|         }
  358|             else if(c == 'c')
  359|                buf[j++] = va_arg(args, int);
  360|             else if(c == 'p'){
  361|                p = va_arg(args, Ptree*);
  362|                if(p == nil)
  363|                  /* ignore */;
  364|                else if(p->IsLeaf()){
  365|                    memmove(&buf[j], p->GetPosition(), p->GetLength());
  366|                    j += p->GetLength();
  367|         }
  368|                else{   
  369|                if(j > 0)
  370|                       q = new DupLeaf(buf, j);
  371|                else
  372|                q = nil;
  373| 
  374|                j = 0;
  375|                    result = Nconc(result, List(q, p));
  376|         }
  377|         }
  378|         else
  379|                MopErrorMessage("Ptree::MakeStatement()", "invalid format");
  380|         }
  381|         else
  382|             buf[j++] = c;
  383| 
  384|     va_end(args);
  385| 
  386|     if(j > 0)
  387|         if(result == nil)
  388|             result = new DupLeaf(buf, j);
  389|         else
  390|             result = Snoc(result, new DupLeaf(buf, j));
  391| 
  392|     return result;
  393| }
  394| 
  395| bool Ptree::Reify(unsigned int& value)
  396| {
  397|     return Lex::Reify(this, value);
  398| }
  399| 
  400| bool Ptree::Reify(char*& str)
  401| {
  402|     return Lex::Reify(this, str);
  403| }
  404| 
  405| char* Ptree::IntegerToString(sint num, int& length)
  406| {
  407|     const int N = 16;
  408|     static char buf[N];
  409|     bool minus;
  410| 
  411|     int i = N - 1;
  412|     if(num >= 0)
  413|         minus = FALSE;
  414|     else{
  415|         minus = TRUE;
  416|         num = -num;
  417|     }
  418| 
  419|     buf[i--] = '\0';
  420|     if(num == 0){
  421|         buf[i] = '0';
  422|         length = 1;
  423|         return &buf[i];
  424|     }
  425|     else{
  426|         while(num > 0){
  427|             buf[i--] = '0' + char(num % 10);
  428|             num /= 10;
  429|         }
  430| 
  431|         if(minus)
  432|             buf[i--] = '-';
  433| 
  434|         length = N - 2 - i;
  435|         return &buf[i + 1];
  436|     }
  437| }
  438| 
  439| Ptree* Ptree::qMake(char*)
  440| {
  441|     MopErrorMessage("Ptree::qMake()",
  442|                    "the metaclass must be compiled by OpenC++.");
  443|     return nil;
  444| }
  445| 
  446| Ptree* Ptree::qMakeStatement(char*)
  447| {
  448|     MopErrorMessage("Ptree::qMakeStatement()",
  449|                    "the metaclass must be compiled by OpenC++.");
  450|     return nil;
  451| }
  452| 
  453| // class PtreeHead      --- this is used to implement Ptree::qM
  454| 
  455| PtreeHead& PtreeHead::operator + (Ptree* p)
  456| {
  457|     ptree = Append(ptree, p);
  458|     return *this;
  459| }
  460| 
  461| PtreeHead& PtreeHead::operator + (const char* str)
  462| {
  463|     if(*str != '\0')
  464|         ptree =  Append(ptree, (char*)str, strlen(str));
  465| 
  466|     return *this;
  467| }
  468| 
  469| PtreeHead& PtreeHead::operator + (char* str)
  470| {
  471|     if(*str != '\0')
  472|         ptree =  Append(ptree, str, strlen(str));
  473| 
  474|     return *this;
  475| }
  476| 
  477| PtreeHead& PtreeHead::operator + (char c)
  478| {
  479|     ptree =  Append(ptree, &c, 1);
  480|     return *this;
  481| }
  482| 
  483| PtreeHead& PtreeHead::operator + (int n)
  484| {
  485|     int len;
  486|     char* str = Ptree::IntegerToString(n, len);
  487|     ptree =  Append(ptree, str, len);
  488|     return *this;
  489| }
  490| 
  491| Ptree* PtreeHead::Append(Ptree* lst, Ptree* tail)
  492| {
  493|     Ptree* last;
  494|     Ptree* p;
  495|     Ptree* q;
  496| 
  497|     if(tail == nil)
  498|         return lst;
  499| 
  500|     if(!tail->IsLeaf() && tail->Length() == 1){
  501|         tail = tail->Car();
  502|         if(tail == nil)
  503|             return lst;
  504|     }
  505| 
  506|     if(tail->IsLeaf() && lst != nil){
  507|         last = Ptree::Last(lst);
  508|         if(last != nil){
  509|             p = last->Car();
  510|             if(p != nil && p->IsLeaf()){
  511|                q = new DupLeaf(p->GetPosition(), p->GetLength(),
  512|                               tail->GetPosition(), tail->GetLength());
  513|                last->SetCar(q);
  514|                return lst;
  515|         }
  516|         }
  517|     }
  518| 
  519|     return Ptree::Snoc(lst, tail);
  520| }
  521| 
  522| Ptree* PtreeHead::Append(Ptree* lst, char* str, int len)
  523| {
  524|     Ptree* last;
  525|     Ptree* p;
  526|     Ptree* q;
  527| 
  528|     if(lst != nil){
  529|         last = Ptree::Last(lst);
  530|         if(last != nil){
  531|             p = last->Car();
  532|             if(p != nil && p->IsLeaf()){
  533|                q = new DupLeaf(p->GetPosition(), p->GetLength(),
  534|                str, len);
  535|                last->SetCar(q);
  536|                return lst;
  537|         }
  538|         }
  539|     }
  540| 
  541|     return Ptree::Snoc(lst, new DupLeaf(str, len));
  542| }