shithub: mc

ref: 2bc852bda98762d3bc01548bf972e3f1b137fbfb
dir: /mi/match.c/

View raw version
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdarg.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#include "parse.h"
#include "mi.h"

typedef struct Dtree Dtree;
struct Dtree {
    /* If the values are equal, go to 'sub'. If 'val' is null, anything matches. */
    Node *patexpr;      /* the full pattern for this node */
    Node **val;         /* pattern values to compare against */
    size_t nval;
    Node **load;        /* expression value being compared */
    size_t nload;
    Dtree **sub;        /* submatch to use if if equal */
    size_t nsub;
    Dtree *any;         /* tree for a wildcard match. */

    /* captured variables and action */
    Node **cap;
    size_t ncap;
    Node *act;

    int id;
};

static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap);
void dtdump(Dtree *dt, FILE *f);

/* We treat all integer types, boolean types, etc, as having 2^n constructors.
 *
 * since, of course, we can't represent all of the constructors for 64 bit
 * integers using 64 bit values, we just approximate it. We'd have failed (run
 * out of memory, etc) long before getting to this code if we actually had that
 * many branches of the switch statements anyways.
 */
static size_t nconstructors(Type *t)
{
    if (!t)
        return 0;

    t = tybase(t);
    switch (t->type) {
        case Tyvoid:    return 0;               break;
        case Tybool:    return 2;               break;
        case Tychar:    return 0x10ffff;        break;

        /* signed ints */
        case Tyint8:    return 0x100;           break;
        case Tyint16:   return 0x10000;         break;
        case Tyint32:   return 0x100000000;     break;
        case Tyint:     return 0x100000000;     break;
        case Tylong:    return ~0ull;           break;
        case Tyint64:   return ~0ull;           break;

        /* unsigned ints */
        case Tybyte:    return 0x100;           break;
        case Tyuint8:   return 0x100;           break;
        case Tyuint16:  return 0x10000;         break;
        case Tyuint32:  return 0x100000000;     break;
        case Tyuint:    return 0x100000000;     break;
        case Tyulong:   return ~0ull;           break;
        case Tyuint64:  return ~0ull;           break;

        /* floats */
        case Tyflt32:   return ~0ull;           break;
        case Tyflt64:   return ~0ull;           break;

        /* complex types */
        case Typtr:     return 1;       break;
        case Tyfunc:    return 0;       break;
        case Tyarray:   return 1;       break;
        case Tytuple:   return 1;       break;
        case Tystruct:  return 1;
        case Tyunion:   return t->nmemb;        break;
        case Tyslice:   return ~0ULL;   break;
        case Tyvar: case Typaram: case Tyunres: case Tyname:
        case Tybad: case Tyvalist: case Tygeneric: case Ntypes:
            die("Invalid constructor type %s in match", tystr(t));
            break;
    }
    return 0;
}

static int ndt;
static Dtree *mkdtree()
{
    Dtree *t;

    t = zalloc(sizeof(Dtree));
    t->id = ndt++;
    return t;
}

static Dtree *addwild(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    if (t->any)
        return t->any;
    t->any = mkdtree();
    t->any->patexpr = pat;
    if (cap && ncap)
        lappend(cap, ncap, pat);
    return t->any;
}

static Dtree *addunion(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    Dtree *sub;
    size_t i;

    if (t->any)
        return t->any;
    /* if we have the value already... */
    sub = NULL;
    for (i = 0; i < t->nval; i++) {
        if (nameeq(t->val[i], pat->expr.args[0])) {
            if (pat->expr.nargs > 1)
                return addpat(t->sub[i], pat->expr.args[1], NULL, cap, ncap);
            else
                return t->sub[i];
        }
    }

    sub = mkdtree();
    sub->patexpr = pat;
    lappend(&t->val, &t->nval, pat->expr.args[0]);
    lappend(&t->sub, &t->nsub, sub);
    if (pat->expr.nargs == 2)
        sub = addpat(sub, pat->expr.args[1], NULL, cap, ncap);
    return sub;
}

static Dtree *addlit(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    Dtree *sub;
    size_t i;

    if (t->any)
        return t->any;
    for (i = 0; i < t->nval; i++) {
        if (liteq(t->val[i]->expr.args[0], pat->expr.args[0]))
            return t->sub[i];
    }

    sub = mkdtree();
    sub->patexpr = pat;
    lappend(&t->val, &t->nval, pat);
    lappend(&t->sub, &t->nsub, sub);
    return sub;
}

static Dtree *addtup(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    size_t i;

    if (t->any)
        return t->any;
    for (i = 0; i < pat->expr.nargs; i++)
        t = addpat(t, pat->expr.args[i], NULL, cap, ncap);
    return t;
}

static Dtree *addarr(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    size_t i;

    if (t->any)
        return t->any;
    for (i = 0; i < pat->expr.nargs; i++)
        t = addpat(t, pat->expr.args[i], NULL, cap, ncap);
    return t;
}

static Dtree *addstruct(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    Node *elt;
    size_t i, j;

    if (t->any)
        return t->any;
    for (i = 0; i < pat->expr.nargs; i++) {
        elt = pat->expr.args[i];
        for (j = 0; j < t->nval; j++) {
            if (!strcmp(namestr(elt->expr.idx), namestr(t->val[j]->expr.idx))) {
                t = addpat(t, pat->expr.args[i], NULL, cap, ncap);
                break;
            }
        }
    }
    return t;
}

static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{
    Dtree *ret;
    Node *dcl;

    if (pat == NULL)
        return t;
    switch (exprop(pat)) {
        case Ovar:
            dcl = decls[pat->expr.did];
            if (dcl->decl.isconst)
                ret = addpat(t, dcl->decl.init, val, cap, ncap);
            else
                ret = addwild(t, pat, val, cap, ncap);
            break;
        case Oucon:
            ret = addunion(t, pat, val, cap, ncap);
            break;
        case Olit:
            ret = addlit(t, pat, val, cap, ncap);
            break;
        case Otup:
            ret = addtup(t, pat, val, cap, ncap);
            break;
        case Oarr:
            ret = addarr(t, pat, val, cap, ncap);
            break;
        case Ostruct:
            ret = addstruct(t, pat, val, cap, ncap);
            break;
        case Ogap:
            ret = addwild(t, pat, val, NULL, NULL);
            break;
        default:
            ret = NULL;
            fatal(pat, "unsupported pattern %s of type %s", opstr[exprop(pat)], tystr(exprtype(pat)));
            break;
    }
    return ret;
}

static int isexhaustive(Dtree *dt)
{
    Type *subt;
    size_t i;

    if (dt->any)
        return 1;

    if (dt->nsub > 0) {
        subt = tybase(exprtype(dt->sub[0]->patexpr));
        if (dt->nsub != nconstructors(subt))
            return 0;
    }
    switch (exprop(dt->patexpr)) {
        case Ovar:
            return 1;
        case Olit:
            return 1;
        case Oucon:
            for (i = 0; i < dt->nsub; i++)
                if (!isexhaustive(dt->sub[i]))
                    return 0;
            return 1;
            break;
        case Otup:
            for (i = 0; i < dt->nsub; i++)
                if (!isexhaustive(dt->sub[i]))
                    return 0;
            return 1;
            break;
        case Oarr:
            for (i = 0; i < dt->nsub; i++)
                if (!isexhaustive(dt->sub[i]))
                    return 0;
            return 1;
            break;
        case Ostruct:
            for (i = 0; i < dt->nsub; i++)
                if (!isexhaustive(dt->sub[i]))
                    return 0;
            return 1;
            break;
        default:
            die("Invalid pattern in exhaustivenes check. BUG.");
            break;
    }
    return 0;
}

static int exhaustivematch(Node *m, Dtree *t, Type *tt)
{
    size_t i;

    if (t->any)
        return 1;
    if (t->nsub != nconstructors(tt))
        return 0;
    for (i = 0; i < t->nsub; i++)
        if (!isexhaustive(t->sub[i]))
            return 0;
    return 1;
}

static Node *genmatch(Dtree *dt)
{
    return NULL;
}

Node *gensimpmatch(Node *m)
{
    Dtree *t, *leaf;
    Node **pat, **cap;
    size_t npat, ncap;
    size_t i;

    pat = m->matchstmt.matches;
    npat = m->matchstmt.nmatches;
    t = mkdtree();
    for (i = 0; i < npat; i++) {
        cap = NULL;
        ncap = 0;
        leaf = addpat(t, pat[i]->match.pat, NULL, &cap, &ncap);
        /* TODO: NULL is returned by unsupported patterns. */
        if (!leaf)
            return NULL;
        if (leaf->act)
            fatal(pat[i], "pattern matched by earlier case on line %d", leaf->act->loc.line);
        leaf->act = pat[i]->match.block;
        leaf->cap = cap;
        leaf->ncap = ncap;
    }
    if (!exhaustivematch(m, t, exprtype(m->matchstmt.val)))
        fatal(m, "nonexhaustive pattern set in match statement");
    return genmatch(t);
}

char *dtnodestr(Node *n)
{
    switch (exprop(n)) {
        case Ovar:
            return namestr(n->expr.args[0]);
        case Olit:
            return litstr[n->expr.args[0]->lit.littype];
        case Oucon:
            return namestr(n->expr.args[0]);
        case Otup:
            return "tuple";
        case Oarr:
            return "array";
        case Ostruct:
            return "struct";
        default:
            die("Invalid pattern in exhaustivenes check. BUG.");
            break;
    }
    return "???";
}

void dtdumpnode(Dtree *dt, FILE *f, int depth, int iswild)
{
    Node *e;
    size_t i;
    char *s;

    if (dt->patexpr) {
        e = dt->patexpr;
        s = tystr(exprtype(e));
        indentf(depth, "%s%s %s : %s\n", iswild ? "WILDCARD " : "", opstr[exprop(e)], dtnodestr(e), s);
        free(s);
    } 
    if (dt->cap)
        for (i = 0; i < dt->ncap; i++)
            indentf(depth + 1, "capture %s\n", dtnodestr(dt->cap[i]));
    if (dt->act)
        indentf(depth + 1, "action\n");
    for (i = 0; i < dt->nsub; i++)
        dtdumpnode(dt->sub[i], f, depth + 1, 0);
    if (dt->any)
        dtdumpnode(dt->any, f, depth + 1, 1);
}

void dtdump(Dtree *dt, FILE *f)
{
    dtdumpnode(dt, f, 0, 0);
}