/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/*        All Rights Reserved   */


/*
 * Copyright (c) 1998-1999 by Sun Microsystems, Inc.
 * All rights reserved.
 */

/* EMACS_MODES: !fill, lnumb, !overwrite, !nodelete, !picture */

#include "assert.h"
#include "string.h"
#include "errno.h"
#include "stdlib.h"

#include "lp.h"
#include "filters.h"

#include "regex.h"


#define MATCH(PT, PM) (STREQU((PT)->pattern, PATT_STAR) || \
                                        match((PT)->re, *((PM)->pvalue)))


typedef struct PARM {
        char                    *keyword;
        unsigned short          flags;
        char                    **pvalue;
}                       PARM;

#define X_MUST  0x0800  /* Pipeline MUST use this parm */
#define X_FIRST 0x1000  /* Use parm only in 1st cmd of pipeline */
#define X_FIXED 0x2000  /* Get value from elsewhere, not parms */
#define X_MANY  0x4000  /* Several values allowed for parm */
#define X_USED  0x8000  /* Used already, don't use again */

static struct S {
        TYPE                    input_type;
        TYPE                    output_type;
        TYPE                    printer_type;
        char                    *printer;
        PARM                    *parms;
} S;

#if     defined(__STDC__)

static int              searchlist_t(TYPE *, TYPE *);
static int              instantiate(_FILTER **, TYPE *, TYPE *,
                                                        int (*)(), void *);
static int              check_pipeline(_FILTER *, PARM *);
static char             *build_pipe(_FILTER *, PARM *, unsigned short *);
#else

static int              searchlist_t();
static int              instantiate();
static int              check_pipeline();
static char             *build_pipe();

#endif

/*
 * Table of recognized keywords, with info. about them.
 */

#define NFIXED 4

static PARM             parmtable[] = {

/* These must be the first NFIXED, and in this order */
PARM_INPUT,     X_FIXED,                        &S.input_type.name,
PARM_OUTPUT,    X_FIXED,                        &S.output_type.name,
PARM_TERM,      X_FIXED,                        &S.printer_type.name,
PARM_PRINTER,   X_FIXED,                        &S.printer,

PARM_CPI,       FPARM_CPI,                      0,
PARM_LPI,       FPARM_LPI,                      0,
PARM_LENGTH,    FPARM_LENGTH,                   0,
PARM_WIDTH,     FPARM_WIDTH,                    0,
PARM_PAGES,     FPARM_PAGES | X_FIRST | X_MUST, 0,
PARM_CHARSET,   FPARM_CHARSET,                  0,
PARM_FORM,      FPARM_FORM,                     0,
PARM_COPIES,    FPARM_COPIES | X_FIRST,         0,
PARM_MODES,     FPARM_MODES | X_MANY | X_MUST,  0,
0,              0,                              0,
};

/*
 * insfilter()
 */

FILTERTYPE
#if     defined(__STDC__)
insfilter(
        char                    **pipes,
        char                    *input_type,
        char                    *output_type,
        char                    *printer_type,
        char                    *printer,
        char                    **parms,
        unsigned short          *flagsp
)
#else
insfilter(pipes, input_type, output_type, printer_type, printer, parms, flagsp)
        char                    **pipes,
                                *input_type,
                                *output_type,
                                *printer_type,
                                *printer,
                                **parms;
        unsigned short          *flagsp;
#endif
{
        _FILTER                 *pipeline;

        FILTERTYPE              ret;


        S.input_type.name = input_type;
        S.input_type.info = isterminfo(input_type);
        S.output_type.name = output_type;
        S.output_type.info = isterminfo(output_type);
        S.printer_type.name = printer_type;
        S.printer_type.info = isterminfo(printer_type);
        S.printer = printer;

        /*
         * If the filters have't been loaded yet, do so now.
         * We'll load the standard table, but the caller can override
         * this by first calling "loadfilters()" with the appropriate
         * filter table name.
         */
        if (!filters && loadfilters((char *)0) == -1)
                return (fl_none);

        /*
         * Allocate and initialize space to hold additional
         * information about each item in "parms".
         * THIS SPACE MUST BE FREED BEFORE EXITING THIS ROUTINE!
         */
        {
                register int            n;

                register PARM *         pp;
                register PARM *         ppt;

                register char **        p;



                for (n = 0, p = parms; *p; n++, p++)
                        ;
                n /= 2;
                n += NFIXED; /* for fixed parms (in/out/printer types) */

                if (!(S.parms = (PARM *)Malloc((n + 1) * sizeof (PARM)))) {
                        errno = ENOMEM;
                        return (fl_none);
                }

                for (ppt = parmtable; ppt->keyword; ppt++)
                        ppt->flags &= ~X_USED;

                /*
                 * Load the parameter list with the fixed ``type''
                 * parameters. Mark them as used (if appropriate)
                 * so we don't pick them up from the callers list.
                 */
                pp = S.parms;
                for (ppt = parmtable; ppt < parmtable + NFIXED; ppt++) {
                        pp->keyword = ppt->keyword;
                        pp->flags = ppt->flags;
                        if (ppt->flags & X_FIXED)
                                pp->pvalue = ppt->pvalue;
                        else
                                pp->pvalue = parms + 1;
                        if (!(ppt->flags & X_MANY))
                                ppt->flags |= X_USED;
                        pp++;
                }

                /*
                 * Copy each parameter from the caller supplied list
                 * to another list, adding information gathered from
                 * the keyword table. Note that some keywords should
                 * be given only once; additional occurrances in the
                 * caller's list will be ignored.
                 */
                for (p = parms; *p; p += 2)
                        for (ppt = parmtable; ppt->keyword; ppt++)
                                if (STREQU(*p, ppt->keyword) &&
                                                !(ppt->flags & X_USED)) {

                                        pp->keyword = ppt->keyword;
                                        pp->flags = ppt->flags;
                                        if (ppt->flags & X_FIXED)
                                                pp->pvalue = ppt->pvalue;
                                        else
                                                pp->pvalue = p + 1;

                                        if (!(ppt->flags & X_MANY))
                                                ppt->flags |= X_USED;

                                        pp++;
                                        break;

                                }

                pp->keyword = 0;

        }

        /*
         * Preview the list of filters, to rule out those that
         * can't possibly work.
         */
        {
                register _FILTER *      pf;

                for (pf = filters; pf->name; pf++) {

                        pf->mark = FL_CLEAR;

                        if (printer && !searchlist(printer, pf->printers))
                                pf->mark = FL_SKIP;

                        else if (printer_type &&
                                        !searchlist_t(&(S.printer_type),
                                                        pf->printer_types))
                                pf->mark = FL_SKIP;

                }
        }

        /*
         * Find a pipeline that will convert the input-type to the
         * output-type and map the parameters as well.
         */
        if (!instantiate(&pipeline, &S.input_type, &S.output_type,
                        check_pipeline, S.parms)) {
                ret = fl_none;
                goto Return;
        }

        if (!pipes) {
                ret = fl_both;
                goto Return;

        } else {
                register _FILTER *      pf;
                register _FILTER *      pfastf; /* first in fast pipe */
                register _FILTER *      pslowf; /* last in slow pipe */

                /*
                 * Found a pipeline, so now build it.
                 */

                /*
                 * Split pipeline after last slow filter.
                 * "pipeline" will point to first filter in slow
                 * pipe, "pfastf" will point to first filter in
                 * fast pipe.
                 */
                for (pf = pfastf = pipeline, pslowf = 0; pf; pf = pf->next)
                        if (pf->type == fl_slow) {
                                pslowf = pf;
                                pfastf = pf->next;
                        }

                if (pslowf) {
                        assert(pslowf != pfastf);
                        pslowf->next = 0;
                        pipes[0] = build_pipe(pipeline, S.parms, flagsp);
                        ret = fl_slow;
                } else
                        pipes[0] = 0;

                if (pfastf) {
                        pipes[1] = build_pipe(pfastf, S.parms, flagsp);
                        ret = fl_fast;
                } else
                        pipes[1] = 0;

                if (pslowf && pfastf)
                        ret = fl_both;

                /*
                 * Check for the oops case.
                 */
                if (pslowf && !pipes[0] || pfastf && !pipes[1])
                        ret = fl_none;

        }

Return: Free((char *)S.parms);

        return (ret);
}

/*
 * searchlist_t() - SEARCH (TYPE *) LIST FOR ITEM
 */

static int
#if     defined(__STDC__)
typematch(
        TYPE                    *type1,
        TYPE                    *type2
)
#else
typematch(type1, type2)
        TYPE                    *type1, *type2;
#endif
{
        if (STREQU(type1->name, NAME_ANY) || STREQU(type2->name, NAME_ANY) ||
                        STREQU(type1->name, type2->name) ||
                        (STREQU(type1->name, NAME_TERMINFO) && type2->info) ||
                        (STREQU(type2->name, NAME_TERMINFO) && type1->info))
                return (1);
        else
                return (0);
}

static int
#if     defined(__STDC__)
searchlist_t(
        TYPE                    *itemp,
        TYPE                    *list
)
#else
searchlist_t(itemp, list)
        TYPE                    *itemp;
        register TYPE           *list;
#endif
{
        if (!list || !list->name)
                return (0);

        /*
         * This is a linear search--we believe that the lists
         * will be short.
         */
        while (list->name) {
                if (typematch(itemp, list))
                        return (1);
                list++;
        }
        return (0);
}

/*
 * instantiate() - CREATE FILTER-PIPELINE KNOWING INPUT/OUTPUT TYPES
 */

/*
 *      The "instantiate()" routine is the meat of the "insfilter()"
 *      algorithm. It is given an input-type and output-type and finds a
 *      filter-pipline that will convert the input-type into the
 *      output-type. Since the filter-pipeline must meet other criteria,
 *      a function "verify" is also given, along with the set of criteria;
 *      these are used by "instantiate()" to verify a filter-pipeline.
 *
 *      The filter-pipeline is built up and returned in "pipeline".
 *      Conceptually this is just a list of filters, with the pipeline to
 *      be constructed by simply concatenating the filter simple-commmands
 *      (after filling in option templates) in the order found in the
 *      list. What is used in the routine, though, is a pair of linked
 *      lists, one list forming the ``right-half'' of the pipeline, the
 *      other forming the ``left-half''. The pipeline is then the two
 *      lists taken together.
 *
 *      The "instantiate()" routine looks for a single filter that matches
 *      the input-type and output-type and satisfies the criteria. If one
 *      is found, it is added to the end of the ``left-half'' list (it
 *      could be added to the beginning of the ``right-half'' list with no
 *      problem). The two lists are linked together to form one linked
 *      list, which is passed, along with the set of criteria, to the
 *      "verify" routine to check the filter-pipeline. If it passes the
 *      check, the work is done.
 *
 *      If a single filter is not found, "instantiate()" examines all
 *      pairs of filters where one in the pair can accept the input-type
 *      and the other can produce the output-type. For each of these, it
 *      calls itself again to find a filter that can join the pair
 *      together--one that accepts as input the output-type of the first
 *      in the pair, and produces as output the input-type of the second
 *      in the pair.  This joining filter may be a single filter or may
 *      be a filter-pipeline. "instantiate()" checks for the trivial case
 *      where the input-type is the output-type; with trivial cases it
 *      links the two lists without adding a filter and checks it with
 *      "verify".
 */

/*
 * instantiate()
 */

/*
 * A PIPELIST is what is passed to each recursive call to "instantiate()".
 * It contains a pointer to the end of the ``left-list'', a pointer to the
 * head of the ``right-list'', and a pointer to the head of the left-list.
 * The latter is passed to "verify". The end of the right-list (and thus
 * the end of the entire list when left and right are joined) is the
 * filter with a null ``next'' pointer.
 */
typedef struct PIPELIST {
        _FILTER *               lhead;
        _FILTER *               ltail;
        _FILTER *               rhead;
}                       PIPELIST;

#if     defined(__STDC__)
static int              _instantiate(PIPELIST *, TYPE *, TYPE *,
                                        int (*)(_FILTER *, void *), void *);
#else
static int              _instantiate();
#endif

static int              peg;

static int
#if     defined(__STDC__)
instantiate(
        _FILTER                 **pline,
        TYPE                    *input,
        TYPE                    *output,
        int                     (*verify)(_FILTER *, void *),
        void                    *criteria
)
#else
instantiate(pline, input, output, verify, criteria)
        _FILTER                 **pline;
        TYPE                    *input,
                                *output;
        int                     (*verify)();
        char                    *criteria;
#endif
{
        PIPELIST                p;
        int                     ret;

        peg = 0;
        p.lhead = p.ltail = p.rhead = 0;
        ret = _instantiate(&p, input, output, verify, criteria);
        *pline = p.lhead;
        return (ret);
}

#define ENTER()         int our_tag; our_tag = ++peg;

#define LEAVE(Y)        if (!Y) { \
                                register _FILTER *f; \
                                for (f = filters; f->name; f++) \
                                        CLEAR(f); \
                                return (0); \
                        } else \
                                return (1)

#define MARK(F, M)      (((F)->mark |= M), (F)->level = our_tag)

#define CLEAR(F)        if ((F)->level == our_tag) \
                                (F)->level = 0, (F)->mark = FL_CLEAR

#define CHECK(F, M)     (((F)->mark & M) && (F)->level == our_tag)

#define USED(F)         ((F)->mark)

static int
#if     defined(__STDC__)
_instantiate(
        PIPELIST                *pp,
        TYPE                    *inputp,
        TYPE                    *outputp,
        int                     (*verify)(_FILTER *, void *),
        void                    *criteria
)
#else
_instantiate(pp, inputp, outputp, verify, criteria)
        PIPELIST                *pp;
        TYPE                    *inputp,
                                *outputp;
        int                     (*verify)();
        char                    *criteria;
#endif
{
        register _FILTER        *prev_lhead;
        register _FILTER        *prev_ltail;


        /*
         * Must be first ``statement'' after declarations.
         */
        ENTER();

        /*
         * We're done when we've added filters on the left and right
         * that let us connect the left and right directly; i.e. when
         * the output of the left is the same type as the input of the
         * right. HOWEVER, there must be at least one filter involved,
         * to allow the filter feature to be used for handling modes,
         * pages, copies, etc. not just FILTERING data.
         */
        if (typematch(inputp, outputp) && pp->lhead) {

                /*
                 * Getting here means that we must have a left and right
                 * pipeline. Why? For "pp->lhead" to be non-zero it
                 * must have been set below. The first place below
                 * doesn't set the right pipeline, but it also doesn't
                 * get us here (at least not directly). The only
                 * place we can get to here again is the second place
                 * "pp->phead" is set, and THAT sets the right pipeline.
                 */
                pp->ltail->next = pp->rhead;
                if ((*verify)(pp->lhead, criteria))
                        LEAVE(1);
                else
                        LEAVE(0);

        }

        /*
         * Each time we search the list of filters, we examine
         * them in the order given and stop searching when a filter
         * that meets the needs is found. If the list is ordered with
         * fast filters before slow filters, then fast filters will
         * be chosen over otherwise-equal filters.
         */

        /*
         * See if there's a single filter that will work.
         * Just in case we can't find one, mark those that
         * will work as left- or right-filters, to save time
         * later.
         *
         * Also, record exactly *which* input/output
         * type would be needed if the filter was used.
         * This record will be complete (both input and output
         * recorded) IF the single filter works. Otherwise,
         * only the input, for the left possible filters,
         * and the output, for the right possible filters,
         * will be recorded. Thus, we'll have to record the
         * missing types later.
         */
        {
                register _FILTER *              pf;


                for (pf = filters; pf->name; pf++) {

                        if (USED(pf))
                                continue;

                        if (searchlist_t(inputp, pf->input_types)) {
                                MARK(pf, FL_LEFT);
                                pf->inputp = inputp;
                        }
                        if (searchlist_t(outputp, pf->output_types)) {
                                MARK(pf, FL_RIGHT);
                                pf->outputp = outputp;
                        }

                        if (CHECK(pf, FL_LEFT) && CHECK(pf, FL_RIGHT)) {
                                prev_lhead = pp->lhead;
                                prev_ltail = pp->ltail;

                                if (!pp->lhead)
                                        pp->lhead = pf;
                                else
                                        pp->ltail->next = pf;
                                (pp->ltail = pf)->next = pp->rhead;

                                if ((*verify)(pp->lhead, criteria))
                                        LEAVE(1);

                                if ((pp->ltail = prev_ltail))
                                        pp->ltail->next = 0;
                                pp->lhead = prev_lhead;

                        }

                }
        }

        /*
         * Try all DISJOINT pairs of left- and right-filters; recursively
         * call this function to find a filter that will connect
         * them (it might be a ``null'' filter).
         */
        {
                register _FILTER *      pfl;
                register _FILTER *      pfr;

                register TYPE *         llist;
                register TYPE *         rlist;


                for (pfl = filters; pfl->name; pfl++) {

                        if (!CHECK(pfl, FL_LEFT))
                                continue;

                        for (pfr = filters; pfr->name; pfr++) {

                                if (pfr == pfl || !CHECK(pfr, FL_RIGHT))
                                        continue;

                                prev_lhead = pp->lhead;
                                prev_ltail = pp->ltail;

                                if (!pp->lhead)
                                        pp->lhead = pfl;
                                else
                                        pp->ltail->next = pfl;
                                (pp->ltail = pfl)->next = 0;

                                pfr->next = pp->rhead;
                                pp->rhead = pfr;

                                /*
                                 * Try all the possible output types of
                                 * the left filter with all the possible
                                 * input types of the right filter. If
                                 * we find a combo. that works, record
                                 * the output and input types for the
                                 * respective filters.
                                 */
                                for (llist = pfl->output_types; llist->name;
                                                                llist++)
                                        for (rlist = pfr->input_types;
                                                        rlist->name; rlist++)
                                                if (_instantiate(pp, llist,
                                                                rlist, verify,
                                                                criteria)) {
                                                        pfl->outputp = llist;
                                                        pfr->inputp = rlist;
                                                        LEAVE(1);
                                                }
                                pp->rhead = pfr->next;
                                if ((pp->ltail = prev_ltail))
                                        pp->ltail->next = 0;
                                pp->lhead = prev_lhead;

                        }

                }
        }

        LEAVE(0);
}

/*
 * check_pipeline() - CHECK THAT PIPELINE HANDLES MODES, PAGE-LIST
 */

static int
#if     defined(__STDC__)
check_pipeline(
        _FILTER                 *pipeline,
        PARM                    *parms
)
#else
check_pipeline(pipeline, parms)
        _FILTER                 *pipeline;
        PARM                    *parms;
#endif
{
        register PARM           *pm;

        register _FILTER        *pf;

        register TEMPLATE       *pt;

        register int            fail;


        for (fail = 0, pm = parms; !fail && pm->keyword; pm++) {

                if (!(pm->flags & X_MUST))
                        continue;

                for (pf = pipeline; pf; pf = pf->next) {

                        if (!(pt = pf->templates))
                                continue;

                        for (; pt->keyword; pt++)
                                if (STREQU(pt->keyword, pm->keyword) &&
                                                pt->result && MATCH(pt, pm))
                                        goto Okay;

                }
                fail = 1;
                continue;

Okay:;

        }

        return (fail? 0 : 1);
}

/*
 * build_filter() - CONSTRUCT PIPELINE FROM LINKED LIST OF FILTERS
 */

#if     defined(__STDC__)
static size_t           build_simple_cmd(char **, _FILTER *, PARM *,
                                                        unsigned short *);
#else
static size_t           build_simple_cmd();
#endif

static char *
#if     defined(__STDC__)
build_pipe(
        _FILTER                 *pipeline,
        PARM                    *parms,
        unsigned short          *fp
)
#else
build_pipe(pipeline, parms, fp)
        _FILTER                 *pipeline;
        PARM                    *parms;
        unsigned short          *fp;
#endif
{
        register _FILTER        *pf;

        register size_t         nchars;
        register size_t         n;

        char                    *p;     /* NOT register */
        char                    *ret;


        /*
         * This is a two-pass routine. In the first pass we add
         * up how much space is needed for the pipeline, in the second
         * pass we allocate the space and construct the pipeline.
         */

        for (nchars = 0, pf = pipeline; pf; pf = pf->next)
                if ((n = build_simple_cmd((char **)0, pf, parms, fp)) > 0)
                        nchars += n + 1;   /* +1 for '|' or ending null */

        if (!(ret = p = Malloc(nchars))) {
                errno = ENOMEM;
                return (0);
        }

        for (pf = pipeline; pf; pf = pf->next, *p++ = (pf? '|' : 0))
                (void) build_simple_cmd(&p, pf, parms, fp);

        return (ret);
}

/*
 * build_simple_cmd()
 */

static size_t
#if     defined(__STDC__)
build_simple_cmd(
        char                    **pp,
        _FILTER                 *pf,
        PARM                    *parms,
        unsigned short          *flagsp
)
#else
build_simple_cmd(pp, pf, parms, flagsp)
        char                    **pp;
        _FILTER                 *pf;
        PARM                    *parms;
        unsigned short          *flagsp;
#endif
{
        register size_t         ncount;

        register TEMPLATE       *pt;

        register PARM           *pm;


        if (pf->command) {
                ncount = strlen(pf->command);
                if (pp) {
                        strcpy (*pp, pf->command);
                        *pp += ncount;
                }
        } else
                ncount = 0;

        if (!pf->templates)
                return (ncount);

        for (pm = parms; pm->keyword; pm++) {

                if ((pm->flags & X_USED) || !*(pm->pvalue))
                        continue;

                for (pt = pf->templates; pt->keyword; pt++) {

                        if (!STREQU(pt->keyword, pm->keyword) || !pt->result)
                                continue;

                        /*
                         * INPUT and OUTPUT are those for *this* filter,
                         * not for the entire pipeline.
                         */
                        if (STREQU(pt->keyword, PARM_INPUT))
                                pm->pvalue = &(pf->inputp->name);
                        else if (STREQU(pt->keyword, PARM_OUTPUT))
                                pm->pvalue = &(pf->outputp->name);

                        if (MATCH(pt, pm)) {
                                if (pp)
                                        *(*pp)++ = ' ';
                                ncount++;

                                ncount += replace(pp, pt->result,
                                                *(pm->pvalue), pt->nbra);

                                /*
                                 * Difficulty here due to the two pass
                                 * nature of this code. The first pass
                                 * just counts the number of bytes; if
                                 * we mark the once-only parms as being
                                 * used, then we don't pick them up the
                                 * second time through. We could get
                                 * difficult and mark them temporarily,
                                 * but that's hard. So on the first pass
                                 * we don't mark the flags. The only
                                 * problem is an estimate too high.
                                 */
                                if (pp && pm->flags & X_FIRST)
                                        pm->flags |= X_USED;

                                *flagsp |= pm->flags;

                        }
                }
        }

        return (ncount);
}