usr/src/usr.bin/lex/ecs.c

/*-
 * Copyright (c) 1990, 1993
 *      The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Vern Paxson of Lawrence Berkeley Laboratory.
 *
 * The United States Government has rights in this work pursuant
 * to contract no. DE-AC03-76SF00098 between the United States
 * Department of Energy and the University of California.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char sccsid[] = "@(#)ecs.c       8.1 (Berkeley) 6/6/93";
#endif /* not lint */

/* ecs - equivalence class routines */

#include "flexdef.h"

/* ccl2ecl - convert character classes to set of equivalence classes
 *
 * synopsis
 *    ccl2ecl();
 */

void ccl2ecl()

    {
    int i, ich, newlen, cclp, ccls, cclmec;

    for ( i = 1; i <= lastccl; ++i )
        {
        /* we loop through each character class, and for each character
         * in the class, add the character's equivalence class to the
         * new "character" class we are creating.  Thus when we are all
         * done, character classes will really consist of collections
         * of equivalence classes
         */

        newlen = 0;
        cclp = cclmap[i];

        for ( ccls = 0; ccls < ccllen[i]; ++ccls )
            {
            ich = ccltbl[cclp + ccls];
            cclmec = ecgroup[ich];

            if ( xlation && cclmec < 0 )
                {
                /* special hack--if we're doing %t tables then it's
                 * possible that no representative of this character's
                 * equivalence class is in the ccl.  So waiting till
                 * we see the representative would be disastrous.  Instead,
                 * we add this character's equivalence class anyway, if it's
                 * not already present.
                 */
                int j;

                /* this loop makes this whole process n^2; but we don't
                 * really care about %t performance anyway
                 */
                for ( j = 0; j < newlen; ++j )
                    if ( ccltbl[cclp + j] == -cclmec )
                        break;

                if ( j >= newlen )
                    { /* no representative yet, add this one in */
                    ccltbl[cclp + newlen] = -cclmec;
                    ++newlen;
                    }
                }

            else if ( cclmec > 0 )
                {
                ccltbl[cclp + newlen] = cclmec;
                ++newlen;
                }
            }

        ccllen[i] = newlen;
        }
    }


/* cre8ecs - associate equivalence class numbers with class members
 *
 * synopsis
 *    int cre8ecs();
 *    number of classes = cre8ecs( fwd, bck, num );
 *
 *  fwd is the forward linked-list of equivalence class members.  bck
 *  is the backward linked-list, and num is the number of class members.
 *
 *  Returned is the number of classes.
 */

int cre8ecs( fwd, bck, num )
int fwd[], bck[], num;

    {
    int i, j, numcl;

    numcl = 0;

    /* create equivalence class numbers.  From now on, abs( bck(x) )
     * is the equivalence class number for object x.  If bck(x)
     * is positive, then x is the representative of its equivalence
     * class.
     */
    for ( i = 1; i <= num; ++i )
        if ( bck[i] == NIL )
            {
            bck[i] = ++numcl;
            for ( j = fwd[i]; j != NIL; j = fwd[j] )
                bck[j] = -numcl;
            }

    return ( numcl );
    }


/* ecs_from_xlation - associate equivalence class numbers using %t table
 *
 * synopsis
 *    numecs = ecs_from_xlation( ecmap );
 *
 *  Upon return, ecmap will map each character code to its equivalence
 *  class.  The mapping will be positive if the character is the representative
 *  of its class, negative otherwise.
 *
 *  Returns the number of equivalence classes used.
 */

int ecs_from_xlation( ecmap )
int ecmap[];

    {
    int i;
    int nul_is_alone = false;
    int did_default_xlation_class = false;

    if ( xlation[0] != 0 )
        {
        /* if NUL shares its translation with other characters, choose one
         * of the other characters as the representative for the equivalence
         * class.  This allows a cheap test later to see whether we can
         * do away with NUL's equivalence class.
         */
        for ( i = 1; i < csize; ++i )
            if ( xlation[i] == -xlation[0] )
                {
                xlation[i] = xlation[0];
                ecmap[0] = -xlation[0];
                break;
                }

        if ( i >= csize )
            /* didn't find a companion character--remember this fact */
            nul_is_alone = true;
        }

    for ( i = 1; i < csize; ++i )
        if ( xlation[i] == 0 )
            {
            if ( did_default_xlation_class )
                ecmap[i] = -num_xlations;

            else
                {
                /* make an equivalence class for those characters not
                 * specified in the %t table
                 */
                ++num_xlations;
                ecmap[i] = num_xlations;
                did_default_xlation_class = true;
                }
            }

        else
            ecmap[i] = xlation[i];

    if ( nul_is_alone )
        /* force NUL's equivalence class to be the last one */
        {
        ++num_xlations;
        ecmap[0] = num_xlations;

        /* there's actually a bug here: if someone is fanatic enough to
         * put every character in its own translation class, then right
         * now we just promoted NUL's equivalence class to be csize + 1;
         * we can handle NUL's class number being == csize (by instead
         * putting it in its own table), but we can't handle some *other*
         * character having to be put in its own table, too.  So in
         * this case we bail out.
         */
        if ( num_xlations > csize )
            flexfatal( "too many %t classes!" );
        }

    return num_xlations;
    }


/* mkeccl - update equivalence classes based on character class xtions
 *
 * synopsis
 *    Char ccls[];
 *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 *    mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping );
 *
 * where ccls contains the elements of the character class, lenccl is the
 * number of elements in the ccl, fwd is the forward link-list of equivalent
 * characters, bck is the backward link-list, and llsiz size of the link-list
 *
 * NUL_mapping is the value which NUL (0) should be mapped to.
 */

void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
Char ccls[];
int lenccl, fwd[], bck[], llsiz, NUL_mapping;

    {
    int cclp, oldec, newec;
    int cclm, i, j;
    static unsigned char cclflags[CSIZE];       /* initialized to all '\0' */

    /* note that it doesn't matter whether or not the character class is
     * negated.  The same results will be obtained in either case.
     */

    cclp = 0;

    while ( cclp < lenccl )
        {
        cclm = ccls[cclp];

        if ( NUL_mapping && cclm == 0 )
            cclm = NUL_mapping;

        oldec = bck[cclm];
        newec = cclm;

        j = cclp + 1;

        for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
            { /* look for the symbol in the character class */
            for ( ; j < lenccl; ++j )
                {
                register int ccl_char;

                if ( NUL_mapping && ccls[j] == 0 )
                    ccl_char = NUL_mapping;
                else
                    ccl_char = ccls[j];

                if ( ccl_char > i )
                    break;

                if ( ccl_char == i && ! cclflags[j] )
                    {
                    /* we found an old companion of cclm in the ccl.
                     * link it into the new equivalence class and flag it as
                     * having been processed
                     */

                    bck[i] = newec;
                    fwd[newec] = i;
                    newec = i;
                    cclflags[j] = 1;    /* set flag so we don't reprocess */

                    /* get next equivalence class member */
                    /* continue 2 */
                    goto next_pt;
                    }
                }

            /* symbol isn't in character class.  Put it in the old equivalence
             * class
             */

            bck[i] = oldec;

            if ( oldec != NIL )
                fwd[oldec] = i;

            oldec = i;
next_pt:
            ;
            }

        if ( bck[cclm] != NIL || oldec != bck[cclm] )
            {
            bck[cclm] = NIL;
            fwd[oldec] = NIL;
            }

        fwd[newec] = NIL;

        /* find next ccl member to process */

        for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
            {
            /* reset "doesn't need processing" flag */
            cclflags[cclp] = 0;
            }
        }
    }


/* mkechar - create equivalence class for single character
 *
 * synopsis
 *    int tch, fwd[], bck[];
 *    mkechar( tch, fwd, bck );
 */

void mkechar( tch, fwd, bck )
int tch, fwd[], bck[];

    {
    /* if until now the character has been a proper subset of
     * an equivalence class, break it away to create a new ec
     */

    if ( fwd[tch] != NIL )
        bck[fwd[tch]] = bck[tch];

    if ( bck[tch] != NIL )
        fwd[bck[tch]] = fwd[tch];

    fwd[tch] = NIL;
    bck[tch] = NIL;
    }