/*
* Copyright (c)2004-2010 Cat's Eye Technologies. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 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.
*
* Neither the name of Cat's Eye Technologies 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 COPYRIGHT HOLDERS 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
* COPYRIGHT HOLDERS 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.
*/
/*
* symstr.c
* Symbol strings for 2Iota.
* $Id: symstr.c 518 2010-04-28 17:48:38Z cpressey $
*/
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "symbol.h"
#include "alphabet.h"
#include "symstr.h"
#include "2iota.h"
const char *symstr_bind_result[] = {
"Bound OK",
"Mismatch between Literals",
"String too Short",
"Pattern too Short",
"Bad String!",
"Bad Pattern!",
"Symbol outside Alphabet",
"*NOT IMPLEMENTED*"
};
struct symstr *
symstr_new(void)
{
struct symstr *ss;
MALLOC(ss, symstr, "symbol string");
ss->head = NULL;
ss->tail = NULL;
return(ss);
}
/*
* Creates a literal symstr from a plain string.
* Not used by the scanner/parser.
*/
struct symstr *
symstr_create(struct symbol_table *stab, char *s)
{
struct symstr *ss;
struct symbol *sym;
char word[128];
int i, j;
i = 0;
ss = symstr_new();
while (s[i] != '\0') {
while (isspace((int)s[i]) && s[i] != '\0')
i++;
if (s[i] == '\0')
break;
j = 0;
while (!isspace((int)s[i]) && s[i] != '\0' && j < 128)
word[j++] = s[i++];
word[j] = '\0';
if ((sym = symbol_lookup(stab, word)) == NULL)
sym = symbol_define(stab, word, SYM_TYPE_LITERAL);
symstr_append(ss, sym, NULL, 0, SYMSTR_OP_NOP);
}
return(ss);
}
struct symstr *
symstr_dup(struct symstr *ss)
{
struct symstr *new_ss;
new_ss = symstr_new();
symstr_append_symstr(new_ss, ss);
return(new_ss);
}
void
symstr_free(struct symstr *ss)
{
struct symstr_component *sc, *nsc;
if (ss == NULL)
return;
/*
* Note that this does not free the symbols or alphabets themselves!
* We generally want those to stick around indefinately.
*/
sc = ss->head;
while (sc != NULL) {
nsc = sc->next;
symstr_component_free(sc);
sc = nsc;
}
FREE(ss, "symbol string");
}
void
symstr_component_free(struct symstr_component *sc)
{
if (sc == NULL)
return;
symstr_free(sc->fmode);
FREE(sc, "symbol string component");
}
struct symstr_component *
symstr_component_new(struct symbol *sym, struct symbol *alphasym,
int many, int op)
{
struct symstr_component *sc;
MALLOC(sc, symstr_component, "symbol string component");
sc->sym = sym;
sc->alphasym = alphasym;
sc->many = many;
sc->next = NULL;
sc->prev = NULL;
sc->op = op;
sc->fmode = NULL;
return(sc);
}
struct symstr_component *
symstr_append(struct symstr *ss, struct symbol *sym,
struct symbol *alphasym, int many, int op)
{
struct symstr_component *sc;
sc = symstr_component_new(sym, alphasym, many, op);
if (ss->head == NULL) {
ss->head = sc;
ss->tail = sc;
} else {
sc->prev = ss->tail;
ss->tail->next = sc;
ss->tail = sc;
}
return(sc);
}
struct symstr_component *
symstr_prepend(struct symstr *ss, struct symbol *sym,
struct symbol *alphasym, int many, int op)
{
struct symstr_component *sc;
sc = symstr_component_new(sym, alphasym, many, op);
if (ss->head == NULL) {
ss->head = sc;
ss->tail = sc;
} else {
sc->next = ss->head;
ss->head->prev = sc;
ss->head = sc;
}
return(sc);
}
void
symstr_append_symstr(struct symstr *dest, struct symstr *src)
{
struct symstr_component *sc;
for (sc = src->head; sc != NULL; sc = sc->next)
symstr_append(dest, sc->sym, NULL, 0, SYMSTR_OP_NOP);
}
void
symstr_remove(struct symstr *ss, struct symstr_component *sc)
{
if (sc->prev != NULL)
sc->prev->next = sc->next;
if (sc->next != NULL)
sc->next->prev = sc->prev;
if (ss->head == sc)
ss->head = sc->next;
if (ss->tail == sc)
ss->tail = sc->prev;
sc->next = NULL;
sc->prev = NULL;
symstr_component_free(sc);
}
int
symstr_is_literal(struct symstr *ss)
{
struct symstr_component *sc;
for (sc = ss->head; sc != NULL; sc = sc->next) {
if (sc->sym == NULL || sc->sym->type != SYM_TYPE_LITERAL ||
sc->alphasym != NULL || sc->op != SYMSTR_OP_NOP)
return 0;
}
return 1;
}
/* Assumes both symstr's are literal. */
int
symstr_eq(struct symstr *a, struct symstr *b)
{
struct symstr_component *sca, *scb;
for (sca = a->head, scb = b->head;
sca != NULL && scb != NULL;
sca = sca->next, scb = scb->next) {
if (strcmp(sca->sym->token, scb->sym->token))
return 0;
}
if (sca != NULL || scb != NULL)
return 0;
return 1;
}
/*
* Determine the specificity of the given symstr.
* rank is the overall specificity rank:
* 0: only literals (most specific)
* 1: some single-symbol free variables
* 2: some multi-symbol free variables (least specific)
* order is the number of free variables as apropos to the rank.
*/
void
symstr_specificity(struct symstr *ss, int *rank, int *order)
{
struct symstr_component *sc;
int count_single_freevars = 0;
int count_multi_freevars = 0;
*rank = 0;
*order = 0;
for (sc = ss->head; sc != NULL; sc = sc->next) {
if (sc->alphasym != NULL) {
if (sc->many > 0) {
*rank = 2;
count_multi_freevars++;
} else {
if (*rank == 0)
*rank = 1;
count_single_freevars++;
}
}
}
switch (*rank) {
case 1:
*order = count_single_freevars;
break;
case 2:
*order = count_multi_freevars;
break;
}
}
struct symstr *
symstr_substitute(struct symstr *pat, struct symbol_table *stab)
{
struct symstr *dest;
struct symstr_component *patc;
dest = symstr_new();
for (patc = pat->head; patc != NULL; patc = patc->next) {
if (patc->sym->type == SYM_TYPE_PARAMETER) {
/* variable? insert its bound value */
if (patc->sym->data != NULL) {
symstr_component_substitute(patc, dest,
patc->sym->data);
} else {
fprintf(stderr, "WHACKY: symbol is not bound?\n");
}
} else {
/* literal? just copy it */
symstr_append(dest, patc->sym, NULL, 0, SYMSTR_OP_NOP);
}
}
stab = stab; /* XXX */
return(dest);
}
void
symstr_component_substitute(struct symstr_component *bc, struct symstr *dest,
struct symstr *boundval)
{
int ok = 0;
struct symstr *res = NULL;
while (!ok) {
/* Apply bc->op. */
if (bc->op == SYMSTR_OP_NOP) {
/*
* XXX this could be the name of a local
* parameter, or it could be a literal.
* If it's a parameter, should use boundval.
* Assume it's a literal, for now.
*/
res = symstr_new();
symstr_append(res, bc->sym, NULL, 0, SYMSTR_OP_NOP);
ok = 1;
} else if (bc->op == SYMSTR_OP_SUCC) {
res = symstr_succ(boundval, bc->sym->alpha, &ok);
} else if (bc->op == SYMSTR_OP_PRED) {
res = symstr_pred(boundval, bc->sym->alpha, &ok);
} else if (bc->op == SYMSTR_OP_NEXT) {
res = symstr_next(boundval, bc->sym->alpha, &ok);
} else if (bc->op == SYMSTR_OP_PREV) {
res = symstr_prev(boundval, bc->sym->alpha, &ok);
} else {
/* Complain severely. */
fprintf(stderr, "Not a legal op\n");
ok = 0;
res = NULL;
}
if (ok) {
symstr_append_symstr(dest, res);
} else {
if (bc->fmode != NULL) {
bc = bc->fmode->head;
} else {
/* Complain severely. */
fprintf(stderr, "Failure not handled\n");
}
}
symstr_free(res);
}
}
int
symstr_bind(struct symstr *str, struct symstr *pat, struct symbol_table *stab)
{
struct symstr_component *strc, *patc;
struct alphabet *alpha;
struct symbol *tsym;
strc = str->head;
patc = pat->head;
for (;;) {
if (strc == NULL && patc == NULL)
return(SYMSTR_BIND_OK);
if (strc == NULL)
return(SYMSTR_BIND_STRING_TOO_SHORT);
if (patc == NULL)
return(SYMSTR_BIND_PATTERN_TOO_SHORT);
/* Some bogosity checking - str should not be a pattern! */
if (strc->alphasym != NULL) {
return(SYMSTR_BIND_BAD_STRING);
}
/* Compare components. */
if (patc->alphasym == NULL) {
/* The literal case. */
if (strc->sym == patc->sym) {
strc = strc->next;
patc = patc->next;
continue;
} else {
return(SYMSTR_BIND_LITERAL_MISMATCH);
}
} else {
/* The 'free variable' case. */
if (stab == NULL) {
/*
* No symbol table was passed, so we really
* can't bind anything - assume that this
* only works with a literal (no-free-vars)
* pattern.
*/
return(SYMSTR_BIND_BAD_PATTERN);
}
alpha = patc->alphasym->alpha;
/* Check to see that the symbol is in the given alphabet. */
if (alphabet_lookup(alpha, strc->sym) == NULL)
return(SYMSTR_BIND_OUTSIDE_ALPHABET);
/* Bind it in the given symbol table. */
tsym = symbol_lookup(stab, patc->sym->token);
if (tsym != NULL) {
tsym->data = symstr_new();
if (patc->many) {
/* while it is in the alphabet */
while (strc != NULL &&
alphabet_lookup(alpha, strc->sym) != NULL) {
symstr_append(tsym->data, strc->sym,
NULL, 0, SYMSTR_OP_NOP);
strc = strc->next;
}
} else {
/* just once */
symstr_append(tsym->data, strc->sym,
NULL, 0, SYMSTR_OP_NOP);
strc = strc->next;
}
patc = patc->next;
} else {
/* Bogosity! It *should* be there. */
return(SYMSTR_BIND_BAD_PATTERN);
}
}
}
}
struct symstr *
symstr_succ(struct symstr *ss, struct alphabet *alpha, int *ok)
{
struct symstr *new_ss;
struct symstr_component *sc;
struct symbol *sym;
new_ss = symstr_dup(ss);
*ok = 1;
sc = new_ss->tail;
for (;;) {
sym = symbol_next(sc->sym, alpha);
if (sym != NULL) {
sc->sym = sym;
break;
} else {
sc->sym = alphabet_first(alpha);
sc = sc->prev;
if (sc == NULL) {
symstr_prepend(new_ss, alphabet_first(alpha),
NULL, 0, SYMSTR_OP_NOP);
break;
}
}
}
return(new_ss);
}
struct symstr *
symstr_pred(struct symstr *ss, struct alphabet *alpha, int *ok)
{
struct symstr *new_ss;
struct symstr_component *sc;
struct symbol *sym;
new_ss = symstr_dup(ss);
*ok = 1;
sc = new_ss->tail;
for (;;) {
sym = symbol_prev(sc->sym, alpha);
if (sym != NULL) {
/* There's a prev symbol in the alphabet - use it. */
sc->sym = sym;
break;
} else {
/* We can't find the prev symbol in the alphabet. */
if (sc->prev == NULL) {
/* We are at the leftmost symbol. */
if (sc->next == NULL) {
/* Actually, it's the ONLY symbol. */
*ok = 0;
symstr_free(new_ss);
new_ss = symstr_dup(ss);
break;
} else {
/* Erase this symbol. */
symstr_remove(new_ss, sc);
break;
}
}
/* Wrap around. */
sc->sym = alphabet_last(alpha);
sc = sc->prev;
}
}
return(new_ss);
}
struct symstr *
symstr_prev(struct symstr *ss, struct alphabet *alpha, int *ok)
{
struct symstr *new_ss;
struct symstr_component *sc;
struct symbol *sym;
new_ss = symstr_dup(ss);
sc = new_ss->tail;
sym = symbol_prev(sc->sym, alpha);
if (sym != NULL) {
sc->sym = sym;
*ok = 1;
} else {
*ok = 0;
}
return(new_ss);
}
struct symstr *
symstr_next(struct symstr *ss, struct alphabet *alpha, int *ok)
{
struct symstr *new_ss;
struct symstr_component *sc;
struct symbol *sym;
new_ss = symstr_dup(ss);
sc = new_ss->tail;
sym = symbol_next(sc->sym, alpha);
if (sym != NULL) {
sc->sym = sym;
*ok = 1;
} else {
*ok = 0;
}
return(new_ss);
}
void
symstr_dump(struct symstr *ss)
{
fprintf(stderr, "{");
if (ss == NULL) {
fprintf(stderr, "}");
return;
}
symstr_components_dump(ss->head);
fprintf(stderr, "}");
}
void
symstr_components_dump(struct symstr_component *sc)
{
while (sc != NULL) {
symstr_component_dump(sc);
if (sc->next != NULL)
fprintf(stderr, " ");
sc = sc->next;
}
}
void
symstr_component_dump(struct symstr_component *sc)
{
if (sc->alphasym == NULL) {
if (sc->op == SYMSTR_OP_NOP) {
symbol_print(sc->sym);
} else {
fprintf(stderr, "(");
if (sc->op == SYMSTR_OP_PRED)
fprintf(stderr, "pred ");
else if (sc->op == SYMSTR_OP_SUCC)
fprintf(stderr, "succ ");
else if (sc->op == SYMSTR_OP_PREV)
fprintf(stderr, "prev ");
else if (sc->op == SYMSTR_OP_NEXT)
fprintf(stderr, "next ");
symbol_print(sc->sym);
if (sc->fmode != NULL) {
fprintf(stderr, " | ");
symstr_components_dump(sc->fmode->head);
}
fprintf(stderr, ")");
}
} else {
fprintf(stderr, "(");
symbol_print(sc->sym);
fprintf(stderr, " = ");
symbol_print(sc->alphasym);
if (sc->many)
fprintf(stderr, "+");
fprintf(stderr, ")");
}
}