tmsim

  1/*
  2 * Copyright © 2016-2018 Sören Tempel
  3 *
  4 * This program is free software: you can redistribute it and/or
  5 * modify it under the terms of the GNU Affero General Public
  6 * License as published by the Free Software Foundation, either
  7 * version 3 of the License, or (at your option) any later version.
  8 *
  9 * This program is distributed in the hope that it will be useful,
 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 12 * Affero General Public License for more details.
 13 *
 14 * You should have received a copy of the GNU Affero General Public
 15 * License along with this program. If not, see
 16 * <http://www.gnu.org/licenses/>.
 17 */
 18
 19#include <assert.h>
 20#include <ctype.h>
 21#include <stdio.h>
 22#include <stdlib.h>
 23#include <string.h>
 24
 25#include <sys/types.h>
 26
 27#include "turing.h"
 28#include "util.h"
 29
 30/**
 31 * Macro used to iterate over all entries of a tmmap.
 32 *
 33 * @param MAP Pointer to a tmmap to iterate over.
 34 * @param VARNAME Variable name used for current item.
 35 * @param IDXVARNAME Variable used to iterate through buckets.
 36 */
 37#define MAP_FOREACH(MAP, VARNAME, IDXVARNAME) \
 38	for (IDXVARNAME = 0; IDXVARNAME < MAP->size; IDXVARNAME++) \
 39		for (VARNAME = MAP->entries[IDXVARNAME]; VARNAME; \
 40		     VARNAME = VARNAME->next)
 41
 42/**
 43 * Allocates memory for a tmmap and initializes it.
 44 *
 45 * @param size Amount of buckets that should be used.
 46 * @returns Pointer to the initialized tmmap.
 47 */
 48static tmmap *
 49newtmmap(size_t size)
 50{
 51	size_t i;
 52	tmmap *map;
 53
 54	map = emalloc(sizeof(tmmap));
 55	map->size = size;
 56	map->entries = emalloc(sizeof(mapentry *) * size);
 57
 58	for (i = 0; i < size; i++)
 59		map->entries[i] = NULL;
 60
 61	return map;
 62}
 63
 64/**
 65 * Hash function for bucket hashing.
 66 *
 67 * @param map Map to calculate hash for.
 68 * @param key Key that should be hashed.
 69 * @returns Hash of the given key.
 70 */
 71static size_t
 72hash(tmmap *map, mapkey key)
 73{
 74	/* XXX: A more advanced hashing function could be
 75	 * used here but this is good enough for now. */
 76	return (size_t)key % map->size;
 77}
 78
 79/**
 80 * Allocates memory and initializes a new map entry / bucket for the tmmap.
 81 *
 82 * @param key Key which should be used for this entry.
 83 * @returns Pointer to initialized mapentry.
 84 */
 85static mapentry *
 86newmapentry(mapkey key)
 87{
 88	mapentry *ent;
 89
 90	ent = emalloc(sizeof(mapentry));
 91	ent->key = key;
 92	ent->next = NULL;
 93	return ent;
 94}
 95
 96/**
 97 * Frees allocated memory for a map entry.
 98 *
 99 * @param ent Pointer to map entry which should be freed.
100 */
101static void
102freemapentry(mapentry *ent)
103{
104	mapentry *next;
105
106	assert(ent);
107
108	do {
109		next = ent->next;
110		free(ent);
111		ent = next;
112	} while (ent != NULL);
113}
114
115/**
116 * Adds a new value to the tmmap, if the key is not already present.
117 *
118 * @param map Map to which a key should be added.
119 * @param ent Entry which should be added.
120 * @returns -1 if the key was already present, 0 otherwise.
121 */
122static int
123setval(tmmap *map, mapentry *ent)
124{
125	size_t idx;
126	mapentry *buck, *last, *next;
127
128	idx = hash(map, ent->key);
129	if (!(buck = map->entries[idx])) {
130		map->entries[idx] = ent;
131		return 0;
132	}
133
134	for (last = next = buck; next != NULL; next = next->next) {
135		if (ent->key == next->key)
136			return -1;
137
138		last = next;
139	}
140
141	last->next = ent;
142	return 0;
143}
144
145/**
146 * Reads the associated value for a given key from the map.
147 *
148 * @param map Map to use for key lookup.
149 * @param key Key which should be looked up.
150 * @param dest Pointer to mapentry used to store the associated value.
151 * @returns -1 if a value for the given key didn't exist, 0 otherwise.
152 */
153static int
154getval(tmmap *map, mapkey key, mapentry **dest)
155{
156	size_t idx;
157	mapentry *buck, *next;
158
159	idx = hash(map, key);
160	if (!(buck = map->entries[idx]))
161		return -1;
162
163	for (next = buck; next != NULL && next->key != key; next = next->next)
164		;
165
166	if (next == NULL)
167		return -1;
168
169	*dest = next;
170	return 0;
171}
172
173/**
174 * Allocates memory for a new tape entry and initializes it.
175 *
176 * @param value Symbol of this tape entry.
177 * @param prev Entry on the left hand side of this one.
178 * @param next Entry on the right hand side of this one.
179 * @returns Pointer to the newly created tape entry.
180 */
181static tapeentry *
182newtapeentry(char value, tapeentry *prev, tapeentry *next)
183{
184	tapeentry *entr;
185
186	entr = emalloc(sizeof(tapeentry));
187	entr->value = value;
188	entr->next = next;
189	entr->prev = prev;
190	return entr;
191}
192
193/**
194 * Allocates memory for a new state and initializes it.
195 *
196 * @returns Pointer to the newly created state.
197 */
198tmstate *
199newtmstate(void)
200{
201	tmstate *state;
202
203	state = emalloc(sizeof(tmstate));
204	state->name = 0;
205	state->trans = newtmmap(TRANSMAPSIZ);
206	return state;
207}
208
209/**
210 * Allocates memory for a new turing maschine and initializes it.
211 *
212 * @returns Pointer to the newly created turing maschine.
213 */
214dtm *
215newtm(void)
216{
217	dtm *tm;
218
219	tm = emalloc(sizeof(dtm));
220	tm->states = newtmmap(STATEMAPSIZ);
221	tm->start = 0;
222	tm->tape = newtapeentry(BLANKCHAR, NULL, NULL);
223	tm->accept = emalloc(ACCEPTSTEP * sizeof(tmname));
224	tm->acceptsiz = 0;
225	return tm;
226}
227
228/**
229 * Adds an accepting state (identified by name) to a turing maschine.
230 *
231 * @param tm Turing maschine to which the state should be added.
232 * @param state Name of the state.
233 */
234void
235addaccept(dtm *tm, tmname state)
236{
237	size_t newsiz;
238
239	if (tm->acceptsiz && tm->acceptsiz % ACCEPTSTEP == 0) {
240		newsiz = (tm->acceptsiz + ACCEPTSTEP) * sizeof(tmname);
241		tm->accept = erealloc(tm->accept, newsiz);
242	}
243
244	tm->accept[tm->acceptsiz++] = state;
245}
246
247/**
248 * Adds a new state to an existing turing maschine.
249 *
250 * @param tm Turing maschine to which a state should be added.
251 * @param state State which should be added to the turing maschine.
252 * @returns -1 if a state with the given name already exists, 0 otherwise.
253 */
254int
255addstate(dtm *tm, tmstate *state)
256{
257	int ret;
258	mapentry *entry;
259
260	entry = newmapentry(state->name);
261	entry->data.state = state;
262
263	if ((ret = setval(tm->states, entry)))
264		freemapentry(entry);
265
266	return ret;
267}
268
269/**
270 * Retrieves a state form an exsting turing maschine.
271 *
272 * @param tm Turing machine from which a state should be retrieved.
273 * @param name Name of the state that should be retrieved.
274 * @param dest Pointer to a state which should be used for storing the result.
275 * @returns -1 if the state doesn't exist, 0 otherwise.
276 */
277int
278getstate(dtm *tm, tmname name, tmstate **dest)
279{
280	int ret;
281	mapentry *entry;
282
283	if ((ret = getval(tm->states, name, &entry)))
284		return ret;
285
286	*dest = entry->data.state;
287	return ret;
288}
289
290/**
291 * Adds a transition to an existing turing maschine state.
292 *
293 * @param state State to which a new transition should be added.
294 * @param trans Pointer to the transition which should be added to the state.
295 * @returns -1 if a state with the given symbol already exists, 0 otherwise.
296 */
297int
298addtrans(tmstate *state, tmtrans *trans)
299{
300	int ret;
301	mapentry *entry;
302
303	entry = newmapentry(trans->rsym);
304	entry->data.trans = trans;
305
306	if ((ret = setval(state->trans, entry)))
307		freemapentry(entry);
308
309	return ret;
310}
311
312/**
313 * Retrieves a transition from an existing turing state.
314 *
315 * @param state State from which a transition should be extracted.
316 * @param rsym Symbol which triggers the tranisition.
317 * @param dest Double pointer used for storing the result.
318 * @returns -1 if a transition with the given symbol doesn't exist, 0 otherwise.
319 */
320int
321gettrans(tmstate *state, char rsym, tmtrans **dest)
322{
323	int ret;
324	mapentry *entry;
325
326	if ((ret = getval(state->trans, rsym, &entry)))
327		return ret;
328
329	*dest = entry->data.trans;
330	return ret;
331}
332
333/**
334 * Writes the given string to the tape of the given turing maschine.
335 *
336 * @param tm Turing machine to modify tape of.
337 * @param str String which should be written to the tape.
338 */
339void
340writetape(dtm *tm, char *str)
341{
342	char c;
343	tapeentry *ent, *last;
344
345	last = tm->tape;
346	for (ent = tm->tape; ent; ent = ent->next)
347		last = ent;
348	assert(last);
349
350	while ((c = *str++)) {
351		ent = newtapeentry(c, last, NULL);
352		last->next = ent;
353		last = ent;
354	}
355}
356
357/**
358 * Writes the content of the tape to STDOUT. The output is always
359 * terminated by a newline character.
360 *
361 * The tape is (theoretically speaking) infinite but since we don't have
362 * infinite amounts of memory we only generate the blanks on the
363 * beginning and end of the tape when you access them. Therefore, the
364 * output will contain as many blanks as accessed by the caller.
365 *
366 * However, the output might start with a blank even if you didn't access
367 * the left-hand side of the tape since the turing machines tape is by
368 * default initialized with a single blank character.
369 *
370 * @param tm Turing machine whose tape should be read.
371 */
372void
373printtape(dtm *tm)
374{
375	tapeentry *c, *s;
376
377	for (s = tm->tape; s->prev; s = s->prev)
378		;
379
380	for (c = s; c; c = c->next)
381		putchar(c->value);
382	putchar('\n');
383}
384
385/**
386 * Whether or not the given state name maps to an accepting state.
387 *
388 * @param tm Turing machine which defines the accepting states.
389 * @param name State name to check.
390 * @returns 0 if it does, -1 if it doesn't.
391 */
392static int
393isaccepting(dtm *tm, tmname name)
394{
395	size_t i;
396
397	for (i = 0; i < tm->acceptsiz; i++)
398		if (tm->accept[i] == name)
399			return 0;
400
401	return -1;
402}
403
404/**
405 * Performs transitions form the given state tail recursively until a state
406 * without any new transitions for the current tape symbol is reached.
407 *
408 * @param tm Turing machine to perform transitions on.
409 * @param state State to perform transitions from.
410 * @return 0 if the reached state is an accepting state, -1 otherwise.
411 */
412static int
413compute(dtm *tm, tmstate *state)
414{
415	char in;
416	tmtrans *trans;
417	static tmstate *next; /* static to enable tail call optimization. */
418
419	if (!tm->tape->next)
420		tm->tape->next = newtapeentry(BLANKCHAR, tm->tape, NULL);
421
422	in = tm->tape->next->value;
423	if (gettrans(state, in, &trans))
424		return isaccepting(tm, state->name);
425
426	tm->tape->next->value = trans->wsym;
427	switch (trans->headdir) {
428	case RIGHT:
429		tm->tape = tm->tape->next;
430		break;
431	case LEFT:
432		if (!tm->tape->prev)
433			tm->tape->prev = newtapeentry(BLANKCHAR, NULL,
434			                              tm->tape);
435		tm->tape = tm->tape->prev;
436		break;
437	case STAY:
438		/* Nothing to do here. */
439		break;
440	}
441
442	if (getstate(tm, trans->nextstate, &next))
443		return isaccepting(tm, trans->nextstate);
444
445	return compute(tm, next);
446}
447
448/**
449 * Starts the turing machine. Meaning it will extract the initial state from
450 * the given tm and will perform transitions (tail recursively) from this state
451 * until a state without any further transitions is reached.
452 *
453 * @param tm Turing machine which should be started.
454 * @return 0 if the reached state is an accepting state, -1 otherwise.
455 */
456int
457runtm(dtm *tm)
458{
459	tmstate *start;
460
461	/* tm->tape->next is only NULL here if the user supplied the
462	 * empty word as an input for this turing maschine. In that
463	 * case we don't want to perform any further transitions. */
464	if (getstate(tm, tm->start, &start) || !tm->tape->next)
465		return isaccepting(tm, tm->start);
466
467	return compute(tm, start);
468}
469
470/**
471 * Iterates over each state of the given turing machine and
472 * invokes the given function for that state.
473 *
474 * @param tm Turing machine to iterate over.
475 * @param fn Function to invoke for each state.
476 * @param arg Additional argument to passed to the function.
477 */
478void
479eachstate(dtm *tm, void (*fn)(tmstate *, void *), void *arg)
480{
481	size_t i;
482	mapentry *elem;
483
484	MAP_FOREACH (tm->states, elem, i)
485		(*fn)(elem->data.state, arg);
486}
487
488/**
489 * Iterates over each transition of the given state and invokes
490 * the given function for that transition
491 *
492 * @param state Turing state to iterate over.
493 * @param fn Function to invoke for each state.
494 * @param arg Additional argument passed to the function.
495 */
496void
497eachtrans(tmstate *state, void (*fn)(tmtrans *, tmstate *, void *), void *arg)
498{
499	size_t i;
500	mapentry *elem;
501
502	MAP_FOREACH (state->trans, elem, i)
503		(*fn)(elem->data.trans, state, arg);
504}
505
506/**
507 * Returns a char representation for a head direction.
508 *
509 * @param dir Head direction which should be converted.
510 * @returns Char describing the direction.
511 */
512int
513dirstr(direction dir)
514{
515	switch (dir) {
516	case RIGHT:
517		return 'r';
518	case LEFT:
519		return 'l';
520	case STAY:
521		return 'n';
522	}
523
524	/* Never reached. */
525	return -1;
526}
527
528/**
529 * Verifies the given input string ensuring that it only consists of
530 * alphanumeric characters and digits. Besides it ensures that it doesn't
531 * contain the special blank symbol.
532 *
533 * @param str Pointer to a string which should be verified.
534 * @param res Pointer to an address where the position
535 * 	of the first character that wasn't valid input should be
536 * 	stored. The first element is assigned position 0.
537 * @returns 0 if the input isn't valid or a non-zero number if it is.
538 */
539int
540verifyinput(char *str, size_t *res)
541{
542	size_t pos;
543	char ch;
544
545	pos = 0;
546	while ((ch = *str++)) {
547		if (!isalnum(ch) || ch == BLANKCHAR) {
548			*res = pos;
549			return 0;
550		}
551		pos++;
552	}
553
554	return -1;
555}