ptreeutil.cc

来自「这个程序是关于OpenC＋＋的反射植入机制的编译器」· CC 代码 · 共 961 行 · 第 1/2 页

{
    if(old == tree)
	return newone;
    else if(tree== 0 || tree->IsLeaf())
	return tree;
    else{
	Ptree *head, *head2;
	head = tree->Car();
	if(old == head)
	    head2 = newone;
	else
	    head2 = head;

	Ptree* tail = tree->Cdr();
	Ptree* tail2 = (tail == 0) ? tail : ShallowSubst(newone, old, tail);
	if(head == head2 && tail == tail2)
	    return tree;
	else
	    return Cons(head2, tail2);
    }
}

Ptree* ShallowSubst(Ptree* newone1, Ptree* old1,
			   Ptree* newone2, Ptree* old2, Ptree* tree)
{
    if(old1 == tree)
	return newone1;
    else if(old2 == tree)
	return newone2;
    else if(tree == 0 || tree->IsLeaf())
	return tree;
    else{
	Ptree *head, *head2;
	head = tree->Car();
	if(old1 == head)
	    head2 = newone1;
	else if(old2 == head)
	    head2 = newone2;
	else
	    head2 = head;

	Ptree* tail = tree->Cdr();
	Ptree* tail2 = (tail == 0) ? tail :
			ShallowSubst(newone1, old1, newone2, old2, tail);
	if(head == head2 && tail == tail2)
	    return tree;
	else
	    return Cons(head2, tail2);
    }
}

Ptree* ShallowSubst(Ptree* newone1, Ptree* old1,
			   Ptree* newone2, Ptree* old2,
			   Ptree* newone3, Ptree* old3, Ptree* tree)
{
    if(old1 == tree)
	return newone1;
    else if(old2 == tree)
	return newone2;
    else if(old3 == tree)
	return newone3;
    else if(tree == 0 || tree->IsLeaf())
	return tree;
    else{
	Ptree *head, *head2;
	head = tree->Car();
	if(old1 == head)
	    head2 = newone1;
	else if(old2 == head)
	    head2 = newone2;
	else if(old3 == head)
	    head2 = newone3;
	else
	    head2 = head;

	Ptree* tail = tree->Cdr();
	Ptree* tail2 = (tail == 0) ? tail :
			ShallowSubst(newone1, old1, newone2, old2,
				     newone3, old3, tail);
	if(head == head2 && tail == tail2)
	    return tree;
	else
	    return Cons(head2, tail2);
    }
}

Ptree* ShallowSubst(Ptree* newone1, Ptree* old1,
			   Ptree* newone2, Ptree* old2,
			   Ptree* newone3, Ptree* old3,
			   Ptree* newone4, Ptree* old4, Ptree* tree)
{
    if(old1 == tree)
	return newone1;
    else if(old2 == tree)
	return newone2;
    else if(old3 == tree)
	return newone3;
    else if(old4 == tree)
	return newone4;
    else if(tree == 0 || tree->IsLeaf())
	return tree;
    else{
	Ptree *head, *head2;
	head = tree->Car();
	if(old1 == head)
	    head2 = newone1;
	else if(old2 == head)
	    head2 = newone2;
	else if(old3 == head)
	    head2 = newone3;
	else if(old4 == head)
	    head2 = newone4;
	else
	    head2 = head;

	Ptree* tail = tree->Cdr();
	Ptree* tail2 =  (tail == 0) ? tail :
			ShallowSubst(newone1, old1, newone2, old2,
				     newone3, old3, newone4, old4, tail);
	if(head == head2 && tail == tail2)
	    return tree;
	else
	    return Cons(head2, tail2);
    }
}

Ptree* SubstSublist(Ptree* newsub, Ptree* oldsub, Ptree* lst)
{
    if(lst == oldsub)
	return newsub;
    else
	return Cons(lst->Car(), SubstSublist(newsub, oldsub, lst->Cdr()));
}

/** Mutably makes list <code>q</code> the last element of list <code>p</code>

    @pre <tt><pre>
    
    p=[p1,p2,p3]       q=[q1,q2,q3]
             
    p--> cons          q--> cons
         /  \               /  \
       p1  cons           q1  cons
           /  \               /  \
         p2  cons           q2  cons
             /  \               /  \
           p3   nil           q3   nil
        
    </pre></tt>

    @post <tt><pre>
    
    p=[p1,p2,p3,[q1,q2,q3]]
             
    p--> cons
         /  \             
       p1  cons           
           /  \           
         p2  cons         
             /  \
           p3   cons (new one)
                /  \
        q--> cons  nil
             /  \
           q1  cons     
               /  \     
             q2  cons   
                 /  \   
               q3   nil 
    </pre></tt>
*/
Ptree* Snoc(Ptree* p, Ptree* q)
{
    return Nconc(p, Cons(q, 0));
}

/** Mutable append.

    @pre <tt><pre>
             
    p=[p1,p2,p3]       q=[q1,q2,q3]

    p--> cons          q--> cons
         /  \               /  \
       p1  cons           q1  cons
           /  \               /  \
         p2  cons           q2  cons
             /  \               /  \
           p3   nil           q3   nil
        
    </pre></tt>

    @post <tt><pre>
             
    p=[p1,p2,p3,q1,q2,q3]
    
    p--> cons             
         /  \             
       p1  cons           
           /  \           
         p2  cons         
             /  \         
           p3  cons <-- q           
               /  \
             q1  cons
                 /  \
               q2  cons
                   /  \ 
                 q3   nil
    </pre></tt>

  */
Ptree* Nconc(Ptree* p, Ptree* q)
{
    if(p == 0)
	return q;
    else{
	Last(p)->SetCdr(q);
	return p;
    }
}

Ptree* Nconc(Ptree* p, Ptree* q, Ptree* r)
{
    return Nconc(p, Nconc(q, r));
}

Ptree* Ca_ar(Ptree* p)
{
    while(p != 0 && !p->IsLeaf())
        p = p->Car();
    return p;
}

char* LeftMost(Ptree* p)
{
    if (! p) {
        return 0;
    }
    
    if(p->IsLeaf()) {
        return p->GetPosition();
    }
    else{
	while (p) {
	    char* i = LeftMost(p->Car());
	    if (i) {
		return i;
	    }
	    else {
		p = p->Cdr();
            }
	}
	return 0;
    }
}

char* RightMost(Ptree* p)
{
    if(! p) {
	return 0;
    }
    
    if(p->IsLeaf()) {
	return p->GetPosition() + p->GetLength();
    }
    else{
	int n = Length(p);
	while (n > 0) {
	    char* i = RightMost(Nth(p,--n));
	    if (i) {
		return i;
            }
	}
	return 0;
    }
}



const int MAX = 32;

Ptree** resultsArgs[MAX];
int resultsIndex;

static int CountArgs(char* pat);
static char* SkipSpaces(char* pat);
static char* MatchList(Ptree* list, char* pat);
static char* MatchWord(Ptree* list, char* pat);


static int CountArgs(char* pat)
{
    int n = 0;

    for(char c = *pat; c != '\0'; c = *++pat)
        if(c == '%'){
            c = *++pat;
            if(c == '?' || c == 'r')
                ++n;
        }

    return n;
}

static char* MatchPat(Ptree* list, char* pat)
{
    switch(*pat){
    case '[' :          /* [] means 0 */
        if(list != 0 && list->IsLeaf())
            return 0;
        else
            return MatchList(list, pat + 1);
    case '%' :
        switch(pat[1]){
        case '?' :
            *resultsArgs[resultsIndex++] = list;
            return(pat + 2);
        case '*' :
            return(pat + 2);
        case '_' :
        case 'r' :      /* %_ and %r must be appear in a list */
            return 0;
        default :
            break;
        }
    }

    if(list != 0 && list->IsLeaf())
        return MatchWord(list, pat);
    else
        return 0;
}

static char* MatchList(Ptree* list, char* pat)
{
    char c, d;
    pat = SkipSpaces(pat);
    while((c = *pat) != '\0'){
        if(c == ']')
            if(list == 0)
                return(pat + 1);
            else
                return 0;
        else if(c == '%' && (d = pat[1], (d == 'r' || d == '_'))){
            /* %r or %_ */
            if(d == 'r') 
                *resultsArgs[resultsIndex++] = list;

            list = 0;
            pat = pat + 2;
        }
        else if(list == 0)
            return 0;
        else{
            pat = MatchPat(list->Car(), pat);
            if(pat == 0)
                return 0;

            list = list->Cdr();
        }

        pat = SkipSpaces(pat);
    }

    TheErrorLog().Report(MopMsg(Msg::Fatal, "Ptree::Match()", "unmatched bracket"));
    return 0;
}

static char* MatchWord(Ptree* list, char* pat)
{
    char* str = list->GetPosition();
    int str_len = list->GetLength();

    for(int j = 0; ; ++pat){
        char c = *pat;
        switch(c){
        case '\0' :
        case ' ' :
        case '\t' :
        case '[' :
        case ']' :
            if(j == str_len)
                return pat;
            else
                return 0;
        case '%' :
            c = *++pat;
            switch(c){
            case '[' :
            case ']' :
            case '%' :
                if(j >= str_len || c != str[j++])
                    return 0;

                break;
            default :
                if(j == str_len)
                    return pat;
                else
                    return 0;
            }
            break;
        default :
            if(j >= str_len || c != str[j++])
                return 0;
        }
    }
}

static char* SkipSpaces(char* pat)
{
    while(*pat == ' ' || *pat == '\t')
        ++pat;

    return pat;
}


bool Match(Ptree* list, char* pattern, ...)
{
    va_list args;
    int n = CountArgs(pattern);
    if(n >= MAX)
	TheErrorLog().Report(MopMsg(Msg::Fatal, "Ptree::Match()", "bomb! too many arguments"));

    va_start(args, pattern);
    for(int i = 0; i < n; ++i)
	resultsArgs[i] = va_arg(args, Ptree**);

    va_end(args);

    char* pat = pattern;
    resultsIndex = 0;
    pat = SkipSpaces(pat);
    pat = MatchPat(list, pat);
    if(pat == 0)
	return false;
    else{
	pat = SkipSpaces(pat);
	if(*pat == '\0')
	    return true;
	else{
	    TheErrorLog().Report(MopMsg(Msg::Warning, "Ptree::Match()", std::string("forgotten [ ]?") + pattern));
	    return false;
	}
    }
}


Ptree* GenSym()
{
    static char head[] = "_sym";
    static int seed = 1;
    int len1, len2;

    IntegerToString(seed, len1);

    static unsigned time = 0;
    time++;
    unsigned rnum = time & 0xffff;
    char* num = IntegerToString(rnum, len2);

    int size = len1 + len2 + sizeof(head) - 1 + 1;
    char* name = new (GC) char[size];
    memmove(name, head, sizeof(head) - 1);
    memmove(&name[sizeof(head) - 1], num, len2);
    name[sizeof(head) - 1 + len2] = '_';
    num = IntegerToString(seed++, len1);
    memmove(&name[sizeof(head) - 1 + len2 + 1], num, len1);
    return new Leaf(name, size);
}



} // namespace PtreeUtil

}