/*
 * c3dsearch.c --
 *
 *     This file contains code to implement the "item search" function of
 *     the 3d-canvas. Also to associate and disassociate items from tags.
 */

#include "c3d.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#ifdef CAN3D_WGL
#define strncasecmp  strnicmp
#endif

typedef struct C3dExpr C3dExpr;

/*
 * This macro checks a few invariants that should hold true for all C3dTag
 * structures.
 */
#define CHECK_C3DTAG_POINTERS(pCheck) \
assert(!(pCheck)->pNextItem || (pCheck)->pTag==(pCheck)->pNextItem->pTag);   \
assert(!(pCheck)->pPrevItem || (pCheck)->pTag==(pCheck)->pPrevItem->pTag);   \
assert(!(pCheck)->pNextItem || (pCheck)->pItem!=(pCheck)->pNextItem->pItem); \
assert(!(pCheck)->pPrevItem || (pCheck)->pItem!=(pCheck)->pPrevItem->pItem); \
assert(!(pCheck)->pNextTag || (pCheck)->pItem==(pCheck)->pNextTag->pItem);   \
assert(!(pCheck)->pPrevTag || (pCheck)->pItem==(pCheck)->pPrevTag->pItem);   \
assert(!(pCheck)->pNextTag || (pCheck)->pTag!=(pCheck)->pNextTag->pTag);     \
assert(!(pCheck)->pPrevTag || (pCheck)->pTag!=(pCheck)->pPrevTag->pTag);     \
assert((pCheck)->pItem->pTagList!=(pCheck) || !(pCheck)->pPrevTag);          \
assert((pCheck)->pItem->pTagList==(pCheck) || (pCheck)->pPrevTag);           \

/*
 * Each association between an item and a tag is represented by an instance
 * of the following structure.
 */
struct C3dTag {
  Tcl_Obj *pTag;          /* The tag */
  C3dItem *pItem;         /* The canvas item the holds this tag */
  C3dTag *pNextItem;      /* Next canvas item holding this tag */
  C3dTag *pPrevItem;      /* Previous canvas item holding this tag */
  C3dTag *pNextTag;       /* Next tag on the same canvas item */
  C3dTag *pPrevTag;       /* Previous tag on the same canvas item */
};

/*
 *---------------------------------------------------------------------------
 *
 * checkTagsDb --
 *
 *     Check that the tags database is internally consistent. This function
 *     is only for interactive debugging - even in debug builds it is never
 *     invoked.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     This function executes numerous assert() statements to check
 *     invariants to do with the tags database, so if a problem is
 *     encountered it may not return.
 *
 *---------------------------------------------------------------------------
 */
#ifndef NDEBUG
static void
checkTagsDb(
    C3dWidget *pCanvas
) {
    Tcl_HashSearch search;
    Tcl_HashEntry *pEntry;

    for (pEntry = Tcl_FirstHashEntry(&pCanvas->aItemsByTag, &search);
         pEntry;
         pEntry = Tcl_NextHashEntry(&search)
    ) {
         C3dTag *pTag;
         const char *zTag = Tcl_GetHashKey(&pCanvas->aItemsByTag, pEntry);
         for (pTag = (C3dTag *)Tcl_GetHashValue(pEntry);
              pTag;
              pTag = pTag->pNextItem
         ) {
             assert(0 == strcmp(zTag, Tcl_GetString(pTag->pTag)));
             CHECK_C3DTAG_POINTERS(pTag);
         }
    }
    if (0) {checkTagsDb(0);}
}
#endif

/* Possible values of C3dExpr.type. The lower the integer value the higher
 * precedence the operator has.
 *
 * OP_EOF, OP_LP, OP_RP, OP_SPACE and OP_COMMA do not appear in an
 * expression tree. They are used while compiling expression text into a
 * tree structure only.
 *
 * OP_NONE is used to represent an empty expression. It matches no items.
 */
#define OP_TAG     1      /* A TAG literal */
#define OP_ID      2      /* An integer literal referring to a item */
#define OP_XY      3      /* A view(x,y) expression */
#define OP_TYPE    4      /* A type(...) expression */
#define OP_HIDDEN  5      /* The magic word "hidden" */
#define OP_ALL     6      /* The magic word "all" */
#define OP_NOT     7      /* The ! operator */
#define OP_XOR     8      /* The ^ operator */
#define OP_AND     9      /* The && operator */
#define OP_OR      10     /* The || operator */

#define OP_LP      11     /* "(" */
#define OP_RP      12     /* ")" */

#define OP_EOF     13     /* End-Of-File */
#define OP_SPACE   14     /* Space token */
#define OP_COMMA   15     /* "," */

#define OP_NONE    16


/*
 * Search Algorithm Notes
 *
 *      Parsing and evaluating a search expression is a two stage process.
 *      First, an expression tree made up of instances of the following
 *      structure is constructed to represent the search expression. Once
 *      an expression tree has been constructed, it is evaluated by
 *      iterating through the list of items and evaluating the expression
 *      tree with respect to each one. If the expression evaluates to true
 *      for a certain item, then the item is returned as part of the search
 *      result.
 *
 *      At the moment there are two minor optimizations added to the
 *      algorithm just described:
 *
 *          * The 'head' of the expression tree is allocated on the stack.
 *          * Simple search expressions consisting of a single OP_TAG or
 *            OP_ID element can be evaluated using an index stored as part
 *            of the C3dCanvas object.
 *
 *      It may be posssible to add more optimizations later.
 *
 * Struct C3dExpr Notes
 *
 *      Only a subset of the C3dExpr fields are used by each node of the
 *      expression tree, depending on it's type:
 *
 *          OP_ID  - C3dExpr.id contains the integer id being searched for.
 *          OP_TAG - C3dExpr.zTag contains the tag being searched for.
 *                   C3dExpr.id is the length of zTag in bytes.
 *          OP_XY  - C3dExpr.x and C3dExpr.y contain the viewport coordinates.
 *                   When the expression is evaluated for the first time,
 *                   C3dExpr.zTag is set to point at an OpenGl "hit record"
 *                   array.
 *          OP_ALL - No fields are used.
 *
 *          OP_NOT - C3dExpr.pLeft contains the expression being inverted.
 *          OP_AND - C3dExpr.pLeft and C3dExpr.pRight contain the two
 *                   expressions being logicly combined.
 *          OP_OR  - Same as OP_AND.
 *          OP_XOR - Same as OP_AND.
 *
 */
struct C3dExpr {
    int type;         /* One of the OP_xxx constants */
    int id;
    char *zTag;
    float x1, y1;
    float x2, y2;

    C3dExpr *pLeft;
    C3dExpr *pRight;
    C3dExpr *pParent;
};

/*
 *---------------------------------------------------------------------------
 *
 * viewportEval  --
 *
 *     Argument pExpr points to an expression of type OP_XY. This function
 *     performs two tasks:
 *
 *     * If pExpr->zTag does not point to an OpenGL hit record describing
 *       the primitives that intersect the viewport close to the specified
 *       (x, y) coordinate, then one is created and populated.
 *     * If pItem is not NULL, the function checks if the item is present
 *       in the hit record, returning 1 if it does, or 0 if not.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
viewportEval(
    C3dWidget *pCanvas,
    C3dExpr *pExpr,
    C3dItem *pItem
) {
    GLuint *aHits = 0;

    if (pCanvas->nSelectBufferSize == 0) {
#ifdef NDEBUG
        pCanvas->nSelectBufferSize = 1024;
#else
        pCanvas->nSelectBufferSize = 1;
#endif
    }

    if (!pExpr->zTag) {
        int nHits;

        while (!aHits) {
            int nBytes = pCanvas->nSelectBufferSize * sizeof(GLuint);
            aHits = (GLuint *)C3dAlloc(nBytes);
            memset(aHits, 0, nBytes);

            glSelectBuffer(pCanvas->nSelectBufferSize, aHits);
            glRenderMode(GL_SELECT);

            glInitNames();
            glPushName(0);
            pCanvas->eSelectMode = 1;
            pCanvas->fSelectX1 = pExpr->x1;
            pCanvas->fSelectY1 = pExpr->y1;
            pCanvas->fSelectX2 = pExpr->x2;
            pCanvas->fSelectY2 = pExpr->y2;
            C3d_Canvas_DrawNow(pCanvas);
            pCanvas->eSelectMode = 0;
            glPopName();

            nHits = glRenderMode(GL_RENDER);
            glSelectBuffer(0, 0);
            if (nHits < 0) {
                pCanvas->nSelectBufferSize = pCanvas->nSelectBufferSize * 2;
                assert(aHits);
                C3dFree((char *)aHits);
                aHits = 0;
            }
        }

        assert(aHits);
        pExpr->zTag = (char *)aHits;
        pExpr->id = nHits;
    }

    if (pItem) {
        int id = pItem->id;
        int i;
        int idx = 0;

        aHits = (GLuint *)pExpr->zTag;
        assert(aHits);
        for (i = 0; i < pExpr->id; i++) {
            int j;
            int n = aHits[idx];
            for (j = 0; j < n; j++) {
                if (aHits[idx + 3 + j] == id) {
                    return 1;
                }
            }
            idx += (n + 3);
        }
    }

    return 0;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprMatch --
 *
 *     Evaluate the expression with respect to the supplied canvas item.
 *     Return true if the expression matches, or false otherwise.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
exprMatch(
    C3dExpr *pExpr,
    C3dItem *pItem
) {
    int res = 0;             /* Return value */

    assert(pExpr);
    assert(pItem);

    switch (pExpr->type) {
        case OP_ID:
            res = (pExpr->id == pItem->id);
            break;
        case OP_ALL:
            res = 1;
            break;

        case OP_TAG: {
            C3dTag *pTag;
            int n = pExpr->id;
            const char *z = pExpr->zTag;
            assert(z && n>0);
            for (pTag = pItem->pTagList; pTag; pTag = pTag->pNextTag) {
               const char *zT = Tcl_GetString(pTag->pTag);
               if (strlen(zT) == n && !strncmp(zT, z, n)) {
                  res = 1;
                  break;
               }
            }
            break;
        }
        case OP_AND: {
            assert(pExpr->pLeft && pExpr->pRight);
            if (exprMatch(pExpr->pLeft, pItem) &&
                exprMatch(pExpr->pRight, pItem)
            ) {
                res = 1;
            }
            break;
        }

        case OP_OR: {
            assert(pExpr->pLeft && pExpr->pRight);
            if (exprMatch(pExpr->pLeft, pItem) ||
                exprMatch(pExpr->pRight, pItem)
            ) {
                res = 1;
            }
            break;
        }

        case OP_NOT: {
            assert(pExpr->pLeft);
            if (!exprMatch(pExpr->pLeft, pItem)) {
                res = 1;
            }
            break;
        }

        case OP_XOR: {
            int l;
            int r;
            assert(pExpr->pLeft && pExpr->pRight);
            l = exprMatch(pExpr->pLeft, pItem) ? 1 : 0;
            r = exprMatch(pExpr->pRight, pItem) ? 1 : 0;
            if (l != r) {
                res = 1;
            }
            break;
        }

        case OP_XY: {
            res = viewportEval(pItem->pCanvas, pExpr, pItem);
            break;
        }

        case OP_TYPE: {
            char const *zType = pItem->pType->zType;
            int n = pExpr->id;
            if (strlen(zType) == n && strncmp(zType, pExpr->zTag, n) == 0) {
                res = 1;
            } else {
                res = 0;
            }
            break;
        }

        case OP_HIDDEN: {
            res = pItem->hidden;
            break;
        }

        case OP_NONE: {
            res = 0;
            break;
        }

        default:
            assert(!"Can't happen");
    }

    return res;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprFindIndex --
 *
 *	This routine is used to help decide which query plan to use
 *	when evaluating an expression.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static C3dExpr *
exprFindIndex(
    C3dExpr *pExpr
) {
    assert(pExpr);
    switch (pExpr->type) {
        case OP_XY:
        case OP_TAG:
        case OP_ID:
            return pExpr;
        case OP_AND: {
            C3dExpr *pLeft = exprFindIndex(pExpr->pLeft);
            C3dExpr *pRight = exprFindIndex(pExpr->pRight);
            if (!pRight || (pLeft && pLeft->type == OP_ID)) {
                return pLeft;
            }
            return pRight;
        }
    }
    return 0;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprEvaluate --
 *
 *     Evaluate the supplied expression tree and invoke the callback for
 *     each item stored by pCanvas that the expression matches.
 *
 * Results:
 *     Tcl error code.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
exprEvaluate(
    C3dWidget *pCanvas,
    C3dExpr *pExpr,
    int oneOnly,
    int modifiestags,
    search_callback xCallback,
    ClientData clientData
) {
    /* We have four "query plans" that may be followed, depending on
     * the form of the expression. They are listed below in order of
     * preference:
     *
     * (a) If the query is of the form "ID" or "ID AND <expr>", where ID is
     *     an item id, then do a single lookup on the aItemsById hash
     *     table. If the whole expression matches this item, then invoke
     *     the callback.
     *
     * (b) If the query is of the form "TAG" or "TAG AND <expr>", where TAG
     *     is a tag name, then look up the linked list of items
     *     associated with the tag in the aItemsByTag hash table. For each
     *     of the items in the list that match the whole expression, the
     *     callback is invoked.
     *
     * (c) For "viewport(x,y)" or "viewport(x,y) && <expr>", we draw the
     *     scene in GL_SELECT mode and loop through the resulting hit list.
     *
     * (d) Loop through all the items in the aItemsById hash table. Invoke
     *     the callback for each one that matches the expression.
     */
    C3dExpr *pIndex;
    Tcl_HashEntry *pEntry;

    /* Special case: If the root node of the expression is an OP_NONE, then
     * return early. An empty search expression matches no items.
     */
    if (pExpr->type == OP_NONE) {
        return TCL_OK;
    }

    pIndex = exprFindIndex(pExpr);

    if (pIndex && pIndex->type == OP_ID) {
        /* Query plan (a) */
        long id = pIndex->id;
        pEntry = Tcl_FindHashEntry(&pCanvas->aItemsById, (char *)id);
        if (pEntry) {
            C3dItem *pItem = Tcl_GetHashValue(pEntry);
            if (pIndex == pExpr || exprMatch(pExpr, pItem)) {
                if (xCallback(clientData, pItem)) {
                    return TCL_ERROR;
                }
            }
        }
    } else if (pIndex && pIndex->type == OP_TAG) {
        /* Query plan (b) */
        if (pIndex->id < 32) {
            char zBuf[32];
            strncpy(zBuf, pIndex->zTag, pIndex->id);
            zBuf[pIndex->id] = '\0';
            pEntry = Tcl_FindHashEntry(&pCanvas->aItemsByTag, zBuf);
        } else {
            char *zBuf;
            zBuf = C3dAlloc(pIndex->id+1);
            strncpy(zBuf, pIndex->zTag, pIndex->id);
            zBuf[pIndex->id] = '\0';
            pEntry = Tcl_FindHashEntry(&pCanvas->aItemsByTag, zBuf);
            C3dFree(zBuf);
        }
        if (pEntry) {
            int nItem = 0;
            int i;
            C3dTag *pTag;
            C3dTag *pList = Tcl_GetHashValue(pEntry);

            for (pTag = pList; pTag; pTag = (oneOnly ? 0 : pTag->pNextItem)) {
                C3dItem *pItem;
                CHECK_C3DTAG_POINTERS(pTag);
                pItem = pTag->pItem;
                if (pIndex == pExpr || exprMatch(pExpr, pItem)) {
                    if (modifiestags && !oneOnly) {
                        nItem++;
                    } else {
                        if (xCallback(clientData, pItem)) {
                            return TCL_ERROR;
                        }
                        if (oneOnly) goto finish_search;
                    }
                }
            }

            if (nItem > 0) {
                C3dItem **aItem = (C3dItem **)C3dAlloc(nItem * sizeof(C3dItem));
                i = 0;
                for (pTag = pList; pTag; pTag = pTag->pNextItem) {
                    if (pIndex == pExpr || exprMatch(pExpr, pTag->pItem)) {
                        assert(i < nItem);
                        aItem[i++] = pTag->pItem;
                    }
                }
                assert(i == nItem);
                for (i = 0; i < nItem; i++) {
                    if (xCallback(clientData, aItem[i])) {
                        return TCL_ERROR;
                    }
                }
                C3dFree((char *)aItem);
            }
        }
    } else if (pIndex && pIndex->type == OP_XY) {
        /* Query plan (c) */
        int i;
        int idx = 0;
        GLuint *aHits;

        viewportEval(pCanvas, pIndex, 0);
        aHits = (GLuint *)pIndex->zTag;
        assert(aHits);

        for (i = 0; i < pIndex->id; i++) {
            int j;
            int n = aHits[idx];
            for (j = 0; j < n; j++) {
                long itemid = aHits[idx + 3 + j];
                pEntry = Tcl_FindHashEntry(&pCanvas->aItemsById, (char*)itemid);
                if (pEntry) {
                    C3dItem *pItem = Tcl_GetHashValue(pEntry);
                    if (pIndex == pExpr || exprMatch(pExpr, pItem)) {
                        if (xCallback(clientData, pItem)) {
                            return TCL_ERROR;
                        }
                        if (oneOnly) goto finish_search;
                    }
                }
            }
            idx += (n + 3);
        }
    } else {
        /* Query plan (d) */
        Tcl_HashSearch search;
        assert(!pIndex);

        for(pEntry = Tcl_FirstHashEntry(&pCanvas->aItemsById, &search);
            pEntry;
            pEntry = Tcl_NextHashEntry(&search)
        ) {
            C3dItem *pItem = Tcl_GetHashValue(pEntry);
            if (exprMatch(pExpr, pItem)) {
                if (xCallback(clientData, pItem)) {
                    return TCL_ERROR;
                }
                if (oneOnly) goto finish_search;
            }
        }
    }

finish_search:

    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprGetToken --
 *
 *     This function is used to extract the next token from a search
 *     expression in string form.
 *
 *     *pZ is a pointer to the start of the token to return. After this
 *     function returns *pZ is set to point at the token after the current
 *     one. The integer value returned is one of the OP_xxx values defined
 *     above. Example:
 *
 *         char *zSearchExpression;      // Pointer to search expression
 *
 *         while (*zSearchExpression) {
 *             int nToken;               // Token length
 *             char *zToken;             // Token string
 *             int eType;                // Token type
 *
 *             zToken = zSearchExpression;
 *             eType = exprGetToken(&zSearchExpression);
 *             nToken = zSearchExpression - zToken;
 *
 *             // Do something with token...
 *         }
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
exprGetToken(
    char const **pZ
) {
    int eType = 0;
    char const *z = *pZ;

    assert(*z);

    switch (*z) {
        case 0:
            eType = OP_EOF;

        case ' ': case '\t': case '\n': case '\r':
            while (isspace(*z)) z++;
            eType = OP_SPACE;
            break;

        case '|':
            z++;
            if (*(z++) == '|') {
                eType = OP_OR;
            } else {
                return 0;
            }
            break;

        case '&':
            z++;
            if (*(z++) == '&') {
                eType = OP_AND;
            } else {
                return 0;
            }
            break;

        case '^':
            z++;
            eType = OP_XOR;
            break;

        case ',':
            z++;
            eType = OP_COMMA;
            break;

        case ')':
            z++;
            eType = OP_RP;
            break;

        case '(':
            z++;
            eType = OP_LP;
            break;

        case '!':
            z++;
            eType = OP_NOT;
            break;

        /* A tag name, keyword or id. Not punctuation at any rate. */
        default: {
            char const *zStart = z;
            char const *zTmp;
            eType = OP_TAG;
            while (*z && !isspace(*z) &&
                    *z != ')' && *z != '(' && *z != '!' &&
                    *z != '&' && *z != '|' && *z != '^' &&
                    *z != ','
            ) {
               z++;
            }

            /* The "all" keyword. */
            if ((z - zStart) == 3 && !strncasecmp("all", zStart, 3)) {
                eType = OP_ALL;
            }

            /* The "viewport" keyword. */
            else if ((z - zStart) == 8 && !strncasecmp("viewport", zStart, 8)) {
                eType = OP_XY;
            }

            /* The "type" keyword. */
            else if ((z - zStart) == 4 && !strncasecmp("type", zStart, 4)) {
                eType = OP_TYPE;
            }

            /* The "hidden" keyword. */
            else if ((z - zStart) == 6 && !strncasecmp("hidden", zStart, 6)) {
                eType = OP_HIDDEN;
            }

            /* If all characters are digits, this is an id, not a tag. */
            else {
                for (zTmp = zStart; zTmp < z; zTmp++) {
                    if (!isdigit(*zTmp)) {
                        break;
                    }
                }
                if (zTmp == z) {
                    eType = OP_ID;
                }
            }

            break;
        }
    }

    *pZ = z;
    return eType;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprGetArgs --
 *
 *     This function is used to parse elements of an item search expression
 *     that use function syntax. i.e. (viewport(x,y), hidden(), and
 *     type(x)). It is called whenever a "viewport", "hidden" or "type"
 *     keyword is encountered.
 *
 *     When this function is called, *pzExpr points to the point in the
 *     item search expression string just passed the keyword just parsed.
 *     If the next non-whitespace token scanned is not a left parentheses
 *     - '(' -, then TCL_OK is returned an *pNArg is set to -1. This
 *     indicates that the keyword should be treated as an ordinary tag
 *     name.
 *
 *     Otherwise, if the next token is a left-parentheses, then this
 *     function attempts to read up to mxArg comma-seperated arguments from
 *     the expression. Pointers to the arguments parsed are stored in the
 *     azArg array. The length of each argument, in bytes, is stored in the
 *     anArg array. If parsing is successful, the actual number of
 *     arguments read is written to *pNArg, *pzExpr is updated to point
 *     passed the last byte parsed, and TCL_OK is returned.
 *
 *     If more than mxArg arguments are present, or some other parsing
 *     error occurs, TCL_ERROR is returned.
 *
 * Results:
 *     Tcl result, TCL_ERROR or TCL_OK.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
exprGetArgs(
    char const **pzExpr,    /* IN/OUT: Pointer to current cursor location */
    char const **azArg,     /* Array to store function arguments in */
    int *anArg,             /* Array to store argument lengths in */
    int mxArg,              /* Maximum number of arguments */
    int *pNArg              /* OUT: Actual number of arguments */
) {
    char const *zTmp = *pzExpr;
    int t = 0;
    int n = 0;

    while (*zTmp && (t = exprGetToken(&zTmp)) == OP_SPACE);

    if (t == OP_LP && *zTmp) {
        while (n == 0 || n < mxArg) {
            char const *zArg;
            do {
                zArg = zTmp;
                t = exprGetToken(&zTmp);
            } while (t == OP_SPACE);

            if (n != 0 || t != OP_RP) {
                if (!*zTmp) return TCL_ERROR;
                azArg[n] = zArg;
                anArg[n] = (zTmp - zArg);
                n++;
                while (*zTmp && (t = exprGetToken(&zTmp)) == OP_SPACE);
            }

            if (t == OP_RP) {
                *pNArg = n;
                *pzExpr = zTmp;
                return TCL_OK;
            }
            if (t != OP_COMMA || !*zTmp) return TCL_ERROR;
        }
        return TCL_ERROR;
    }

    *pNArg = -1;
    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprCompile --
 *
 *     This function is used to compile a search expression into a tree
 *     constructed of C3dExpr nodes.
 *
 *     The text of the expression is passed as the second argument, zExpr.
 *
 *     The valid operators, listed in decreasing order of precedence, are:
 *
 *         ! ^ && ||
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
exprCompile(
    C3dWidget *pCanvas,
    char const *zExpr,
    int *pnExpr,
    C3dExpr *pExprOut
) {
    char const *z = zExpr;
    C3dExpr *pExpr = pExprOut;
    char const *zToken = 0;
    int nToken = 0;
    int notempty = 0;

    enum CompilerState {
        EXPECT_EXPRESSION,
        EXPECT_OPERATOR
    };
    enum CompilerState state = EXPECT_EXPRESSION;

    while (*z) {
        int eType;
        zToken = z;

        eType = exprGetToken(&z);
        nToken = (z - zToken);

        notempty++;

        switch(eType) {
            case 0:
                goto syntax_error;

            case OP_SPACE:
            case OP_EOF:
                notempty--;
                break;

            case OP_ID:
                if (state != EXPECT_EXPRESSION) goto syntax_error;
                pExpr->type = eType;
                pExpr->id = strtol(zToken, 0, 10);
                state = EXPECT_OPERATOR;
                break;

            case OP_XY: {
		/* The "viewport" keyword. The correct syntax is
                 * "viewport(x, y)", where x and y are integers. Any other
                 * use of "viewport" falls back to a tag name.
                 */
                Tk_Window win = pCanvas->tkwin;
                char const *zTmp = z;
                char const *azArg[4];
                int anArg[4];
                int nArg;

                float x1, y1;
                float x2, y2;

                if (state != EXPECT_EXPRESSION) goto syntax_error;

                if (exprGetArgs(&zTmp, azArg, anArg, 4, &nArg)) {
                    goto syntax_error;
                }
                if (nArg < 0) {
                    eType = OP_TAG;
                    goto tagtoken;
                }
                if (nArg != 2 && nArg != 4) goto syntax_error;

                x1 = strtod(azArg[0], 0);
                y1 = strtod(azArg[1], 0);
                if (nArg == 2) {
                    int closeenough = pCanvas->options.closeenough;
                    x2 = x1 + closeenough;
                    x1 = x1 - closeenough;
                    y2 = y1 + closeenough;
                    y1 = y1 - closeenough;
                } else {
                    x2 = strtod(azArg[2], 0);
                    y2 = strtod(azArg[3], 0);
                }

                pExpr->type = eType;
                pExpr->x1 = ((float)x1 * 2.0 / (float)Tk_Width(win)) - 1.0;
                pExpr->y1 = ((float)y1 * 2.0 / (float)Tk_Height(win)) - 1.0;
                pExpr->x2 = ((float)x2 * 2.0 / (float)Tk_Width(win)) - 1.0;
                pExpr->y2 = ((float)y2 * 2.0 / (float)Tk_Height(win)) - 1.0;
                state = EXPECT_OPERATOR;
                z = zTmp;
                break;
            }

            case OP_TYPE: {
                /* The "type" keyword. The correct syntax is "type(x)",
                 * where x is some typename. Any other use of "type"
                 * falls back to a tag name.
                 */
                char const *zTmp = z;
                char const *zType;
                int nType;
                int nArg;
                if (state != EXPECT_EXPRESSION) goto syntax_error;

                if (exprGetArgs(&zTmp, &zType, &nType, 1, &nArg)) {
                    goto syntax_error;
                }
                if (nArg < 0) {
                    eType = OP_TAG;
                    goto tagtoken;
                }
                if (nArg == 0) goto syntax_error;

                pExpr->type = eType;
                pExpr->id = nType;
                pExpr->zTag = zType;
                z = zTmp;
                state = EXPECT_OPERATOR;
                break;
            }

            case OP_HIDDEN: {
                /* The "hidden" keyword. The correct syntax is "hidden()",
                 * where x is some typename. Any other use of "hidden"
                 * falls back to a tag name.
                 */
                char const *zTmp = z;
                int nArg = 0;
                if (state != EXPECT_EXPRESSION) goto syntax_error;

                if (exprGetArgs(&zTmp, 0, 0, 0, &nArg)) {
                    goto syntax_error;
                }
                if (nArg < 0) {
                    eType = OP_TAG;
                    goto tagtoken;
                }
                pExpr->type = eType;
                z = zTmp;
                state = EXPECT_OPERATOR;
                break;
            }

tagtoken:
            case OP_ALL:
            case OP_TAG:
                if (state != EXPECT_EXPRESSION) goto syntax_error;
                pExpr->type = eType;
                pExpr->id = nToken;
                pExpr->zTag = zToken;
                state = EXPECT_OPERATOR;
                break;

            case OP_NOT:
                if (state != EXPECT_EXPRESSION) goto syntax_error;
                else {
                    C3dExpr *pNew = (C3dExpr *)C3dAlloc(sizeof(C3dExpr));
                    memset(pNew, 0, sizeof(C3dExpr));
                    pExpr->type = eType;
                    pExpr->pLeft = pNew;
                    pNew->pParent = pExpr;
                    pExpr = pNew;
                }
                break;

            case OP_OR:
            case OP_AND:
            case OP_XOR:
                if (state != EXPECT_OPERATOR) goto syntax_error;
                else {
                    C3dExpr *pNew = (C3dExpr *)C3dAlloc(sizeof(C3dExpr));

                    while (pExpr->pParent && pExpr->pParent->type < eType) {
                        pExpr = pExpr->pParent;
                    }

                    memcpy(pNew, pExpr, sizeof(C3dExpr));
                    pExpr->type = eType;
                    pExpr->pLeft = pNew;
                    pNew->pParent = pExpr;

                    pNew = (C3dExpr *)C3dAlloc(sizeof(C3dExpr));
                    memset(pNew, 0, sizeof(C3dExpr));
                    pExpr->pRight = pNew;
                    pNew->pParent = pExpr;

                    pExpr = pNew;
                    state = EXPECT_EXPRESSION;
                }
                break;

            case OP_LP:
                if (state != EXPECT_EXPRESSION) goto syntax_error;
                else {
                    C3dExpr *pParent = pExpr->pParent;
                    int n = 0;
                    int rc;
                    pExpr->pParent = 0;
                    rc = exprCompile(pCanvas, z, &n, pExpr);
                    pExpr->pParent = pParent;
                    if (rc != TCL_OK) {
                        return rc;
                    }
                    if (n == 0) {
                        goto syntax_error;
                    }
                    z += n;
                    state = EXPECT_OPERATOR;
                }
                break;

            case OP_RP:
                if (state != EXPECT_OPERATOR || !pnExpr) goto syntax_error;
                else {
                    *pnExpr = (z - zExpr);
                    return TCL_OK;
                }
                break;

            default:
                goto syntax_error;
        }
    }

    /* This catches all-whitespace strings passed as search expressions. */
    if (state == EXPECT_EXPRESSION) {
        if (notempty) goto syntax_error;
        pExpr->type = OP_NONE;
    }

    return TCL_OK;

    /* Jump to here if a syntax error occurs. The error message generated
     * refers to the error as "near" the string zToken, length nToken. This
     * won't always be all that accurate, but people are used to such error
     * messages being suspect anywhay.
     */
syntax_error: {
        Tcl_Interp *interp = pCanvas->interp;
        Tcl_Obj *pRet;

        pRet = Tcl_NewStringObj("Syntax error in expression", -1);
        C3dIncrRefCount(pRet);
        if (zToken) {
            Tcl_AppendObjToObj(pRet, Tcl_NewStringObj(" near \"", -1));
            Tcl_AppendObjToObj(pRet, Tcl_NewStringObj(zToken, nToken));
            Tcl_AppendObjToObj(pRet, Tcl_NewStringObj("\"", -1));
        }
        Tcl_SetObjResult(interp, pRet);
        C3dDecrRefCount(pRet);
    }

    return TCL_ERROR;
}

/*
 *---------------------------------------------------------------------------
 *
 * exprDelete --
 *
 *     Free all dynamically allocated memory associated with the expression
 *     tree pExpr. The root of the expression tree is always allocated on
 *     the stack. All other nodes are allocated using C3dAlloc() and so are
 *     freed using C3dFree().
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     pExpr becomes unusable.
 *
 *---------------------------------------------------------------------------
 */
static void exprDelete(
    C3dExpr *pExpr
) {
    if (!pExpr) return;
    exprDelete(pExpr->pLeft);
    exprDelete(pExpr->pRight);
    if (pExpr->type == OP_XY && pExpr->zTag) {
        C3dFree((char *)pExpr->zTag);
    }
    if (pExpr->pParent) {
        C3dFree((char *)pExpr);
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dSearch --
 *
 *     This function interprets and implements the "search" parameter that
 *     some widget sub-commands use.
 *
 *     The second argument, pSearch, contains an item search specification
 *     For each item currently stored by pCanvas that matches the search,
 *     function xCallback (the third argument) is invoked.
 *
 *     The third argument, oneOnly, is true if the search should be
 *     abandoned after the first callback is made. This is used for
 *     commands like [$win gettags] etc.
 *
 *     The arguments to xCallback are a copy of the fifth argument passed
 *     to C3dSearch and a pointer to the C3dItem structure.
 *
 * Results:
 *     A Tcl result. If an error occurs parsing the search specification,
 *     TCL_ERROR is returned and an error message written to
 *     C3dWidget.interp.
 *
 * Side effects:
 *     May modify the result of C3dWidget.interp. Also whatever the
 *     callback function may do.
 *---------------------------------------------------------------------------
 */
int
C3dSearch(
    C3dWidget *pCanvas,
    Tcl_Obj *pSearch,
    int flags,
    search_callback xCallback,
    ClientData clientData
) {
    int rc;
    char const *zSearch;
    C3dExpr sExpr;
    int oneOnly = (flags & SEARCHFLAG_ONEONLY);
    int mt = (flags & SEARCHFLAG_MODIFIES_TAGS);

    zSearch = Tcl_GetString(pSearch);
    memset(&sExpr, 0, sizeof(C3dExpr));
    rc = exprCompile(pCanvas, zSearch, 0, &sExpr);
    if (rc == TCL_OK) {
        rc = exprEvaluate(pCanvas, &sExpr, oneOnly, mt, xCallback, clientData);
    }
    exprDelete(&sExpr);
    return rc;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dAddTagToItem --
 *
 *     Variable pTag contains the name of a tag that is to be associated
 *     with pItem. Modify internal structures to reflect this.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int
C3dAddTagToItem(
    C3dWidget *pCanvas,
    Tcl_Obj *pTag,
    C3dItem *pItem
) {
    C3dTag *pNew;
    C3dTag *pIter;
    char const *zTag;
    char const *zCsr;
    int newtag;
    Tcl_HashEntry *pEntry;

    /* Check the tag name is legal. */
    zTag = Tcl_GetString(pTag);
    for (zCsr = zTag; *zCsr; zCsr++) {
        if (*zCsr == ')' || *zCsr == '(' || *zCsr == '|' ||
            *zCsr == '&' || *zCsr == '^' || *zCsr == '!' ||
            (zCsr == zTag && isdigit((int)*zCsr))
        ) {
            Tcl_Interp *interp = pCanvas->interp;
            Tcl_SetResult(interp, "", TCL_STATIC);
            Tcl_AppendResult(interp, "Illegal tag name: ", zTag, 0);
            return TCL_ERROR;
        }
    }

    /* If the tag is already attached to this item, return early. */
    for (pIter = pItem->pTagList; pIter; pIter = pIter->pNextTag) {
        if (!strcmp(Tcl_GetString(pIter->pTag), zTag)) {
            return TCL_OK;
        }
    }

    pNew = (C3dTag *)C3dAlloc(sizeof(C3dTag));
    memset(pNew, 0, sizeof(C3dTag));

    /* Link the new C3dTag to the item */
    pNew->pItem = pItem;
    pNew->pNextTag = pItem->pTagList;
    pItem->pTagList = pNew;
    if (pNew->pNextTag) {
        assert(!pNew->pNextTag->pPrevTag);
        pNew->pNextTag->pPrevTag = pNew;
    }

    /* Now link it into the aItemsByTag table. */
    pEntry = Tcl_CreateHashEntry(&pCanvas->aItemsByTag, zTag, &newtag);
    pNew->pTag = pTag;
    if (!newtag) {
        C3dTag *pExisting = Tcl_GetHashValue(pEntry);
        assert(pExisting);
        assert(!pExisting->pPrevItem);
        pExisting->pPrevItem = pNew;
        pNew->pNextItem = pExisting;
        pNew->pTag = pExisting->pTag;
    }
    Tcl_SetHashValue(pEntry, pNew);
    C3dIncrRefCount(pNew->pTag);

    CHECK_C3DTAG_POINTERS(pNew);
    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * tagDelete --
 *
 *     Delete pTag and all pointers to it stored by pCanvas. If this means
 *     there are no longer any items associated with the tag in question,
 *     then an entry may be removed from C3dWidget.aItemsById.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static void
tagDelete(
    C3dWidget *pCanvas,
    C3dTag *pTag
) {
    C3dItem *pItem;

    assert(pCanvas);
    assert(pTag);

    CHECK_C3DTAG_POINTERS(pTag);

    /* Remove from the item. */
    pItem = pTag->pItem;
    if (pTag == pItem->pTagList) {
        pItem->pTagList = pTag->pNextTag;
        if (pTag->pNextTag) {
            pItem->pTagList->pPrevTag = 0;
        }
    } else {
        pTag->pPrevTag->pNextTag = pTag->pNextTag;
        if (pTag->pNextTag) {
            assert(pTag->pNextTag->pPrevTag == pTag);
            pTag->pNextTag->pPrevTag = pTag->pPrevTag;
        }
    }

    /* Remove from the tag index. */
    if (!pTag->pPrevItem) {
        Tcl_HashEntry *pEntry;
        char *const zTag = Tcl_GetString(pTag->pTag);
        pEntry = Tcl_FindHashEntry(&pCanvas->aItemsByTag, zTag);
        assert(pEntry);
        assert((C3dTag *)Tcl_GetHashValue(pEntry) == pTag);
        if (pTag->pNextItem) {
            assert(pTag->pNextItem->pPrevItem == pTag);
            pTag->pNextItem->pPrevItem = 0;
            Tcl_SetHashValue(pEntry, pTag->pNextItem);
        } else {
            Tcl_DeleteHashEntry(pEntry);
        }
    } else {

#ifndef NDEBUG
        char *const zTag = Tcl_GetString(pTag->pTag);
        Tcl_HashEntry *pEntry = Tcl_FindHashEntry(&pCanvas->aItemsByTag, zTag);
        assert(pEntry);
        assert((C3dTag *)Tcl_GetHashValue(pEntry) != pTag);
#endif

        pTag->pPrevItem->pNextItem = pTag->pNextItem;
        if (pTag->pNextItem) {
            assert(pTag->pNextItem->pPrevItem == pTag);
            pTag->pNextItem->pPrevItem = pTag->pPrevItem;
        }
    }

    /* Free the memory allocated for the structure. */
    C3dDecrRefCount(pTag->pTag);
    C3dFree((char *)pTag);
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dRemoveTagFromItem --
 *
 *     If it is not NULL, then pTagName contains the name of a tag that is
 *     to be disassociated with item pItem. If pTag is NULL, then all tags
 *     currently attached to pItem should be disassociated.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int
C3dRemoveTagFromItem(
    C3dWidget *pCanvas,
    Tcl_Obj *pTagName,
    C3dItem *pItem
) {
    C3dTag *pTag;
    if (pTagName) {
        char const *zTag = Tcl_GetString(pTagName);
        for (pTag = pItem->pTagList; pTag; pTag = pTag->pNextTag) {
            assert(pTag->pItem == pItem);
            if (!strcmp(zTag, Tcl_GetString(pTag->pTag))) {
                tagDelete(pCanvas, pTag);
                break;
            }
        }
    } else {
        while (pItem->pTagList) {
            tagDelete(pCanvas, pItem->pTagList);
        }
    }

    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dGetTags --
 *
 *     Retrieve the list of tags associated with item pItem. The Tcl object
 *     pOut is set to contain the list.
 *
 * Results:
 *     Tcl result.
 *
 * Side effects:
 *     *pOut is modified.
 *
 *---------------------------------------------------------------------------
 */
int
C3dGetTags(
    C3dItem *pItem,
    Tcl_Obj *pOut
) {
    C3dTag *pTag;

    for (pTag = pItem->pTagList; pTag; pTag = pTag->pNextTag) {
#ifndef NDEBUG
        int rc =
#endif
	Tcl_ListObjReplace(0, pOut, 0, 0, 1, &pTag->pTag);
        assert(rc == TCL_OK);
    }
    return TCL_OK;
}
