Line data Source code
1 : /***************************************************************************//**
2 :
3 : @file instr.c
4 :
5 : @author Stephen Brennan
6 :
7 : @date Created Thursday, 21 January 2016
8 :
9 : @brief Functions for reading and writing virtual machine instructions.
10 :
11 : @copyright Copyright (c) 2016, Stephen Brennan. Released under the Revised
12 : BSD License. See LICENSE.txt for details.
13 :
14 : *******************************************************************************/
15 :
16 : #include <stdlib.h>
17 : #include <stdint.h>
18 : #include <string.h>
19 : #include <ctype.h>
20 : #include <stdbool.h>
21 : #include <unistd.h>
22 :
23 : #include "libstephen/re.h"
24 : #include "libstephen/re_internals.h"
25 :
26 : #define COMMENT ';'
27 :
28 : /*
29 : Declarations for parsing.
30 : */
31 :
32 : enum linetype {
33 : Blank, Label, Code
34 : };
35 : typedef enum linetype linetype;
36 :
37 : char *Opcodes[] = {
38 : "char", "match", "jump", "split", "save", "any", "range", "nrange"
39 : };
40 :
41 : /*
42 : Utilities for input/output
43 : */
44 0 : char *char_to_string(char c)
45 : {
46 : #define CTS_BUFSIZE 5
47 : static char buffer[CTS_BUFSIZE];
48 0 : if (c == ' ') {
49 0 : buffer[0] = '\\';
50 0 : buffer[1] = 'x';
51 0 : buffer[2] = '2';
52 0 : buffer[3] = '0';
53 0 : buffer[4] = '\0'; // space = 0x20
54 0 : } else if (isspace(c)) {
55 0 : switch (c) {
56 : case '\n':
57 0 : buffer[1] = 'n';
58 0 : break;
59 : case '\f':
60 0 : buffer[1] = 'n';
61 0 : break;
62 : case '\r':
63 0 : buffer[1]= 'r';
64 0 : break;
65 : case '\t':
66 0 : buffer[1] = 't';
67 0 : break;
68 : case '\v':
69 0 : buffer[1] = 'v';
70 0 : break;
71 : }
72 0 : buffer[0] = '\\';
73 0 : buffer[2] = '\0';
74 0 : } else if (c == '\0') {
75 0 : buffer[0] = '\0'; // empty string...
76 : } else {
77 0 : buffer[0] = c;
78 0 : buffer[1] = '\0';
79 : }
80 0 : return buffer;
81 : }
82 :
83 0 : void fprintc(FILE *f, char c)
84 : {
85 0 : fprintf(f, "%s", char_to_string(c));
86 0 : }
87 :
88 0 : char string_to_char(char *s) {
89 : unsigned int c;
90 0 : if (s[0] == '\\') {
91 0 : switch (s[1]) {
92 : case 'n':
93 0 : return '\n';
94 : case 'f':
95 0 : return '\f';
96 : case 'r':
97 0 : return '\r';
98 : case 't':
99 0 : return '\t';
100 : case 'v':
101 0 : return '\v';
102 : case 'x':
103 0 : sscanf(s + 2, "%x", &c);
104 0 : return (char)c;
105 : default:
106 0 : return s[1];
107 : }
108 : } else {
109 0 : return s[0];
110 : }
111 : }
112 :
113 :
114 : /**
115 : @brief Remove leading and trailing whitespace and comments from a line.
116 : */
117 0 : static char *trim(char *line, char *lastchar_out)
118 : {
119 0 : ssize_t firstnonwhite = -1;
120 0 : ssize_t lastnonwhite = -1;
121 : size_t i;
122 :
123 0 : for (i = 0; line[i]; i++) {
124 0 : if (isspace(line[i])) {
125 0 : continue;
126 : }
127 :
128 0 : if (line[i] == COMMENT) {
129 0 : line[i] = '\0';
130 0 : break;
131 : }
132 :
133 0 : if (firstnonwhite == -1) {
134 0 : firstnonwhite = i;
135 : }
136 0 : lastnonwhite = i;
137 : }
138 :
139 0 : if (firstnonwhite == -1) { // all whitespace
140 0 : *lastchar_out = '\0';
141 0 : return line + i;
142 : } else {
143 0 : line[lastnonwhite + 1] = '\0';
144 0 : *lastchar_out = line[lastnonwhite];
145 0 : return line + firstnonwhite;
146 : }
147 : }
148 :
149 0 : static char **tokenize(char *line, size_t *ntok)
150 : {
151 : #define SEP " \n\t\v\f"
152 0 : size_t alloc = 16;
153 0 : char **buf = calloc(alloc, sizeof(char*));
154 :
155 0 : buf[0] = strtok(line, SEP);
156 0 : *ntok = 0;
157 0 : while (buf[*ntok] != NULL) {
158 0 : *ntok += 1;
159 :
160 0 : if (*ntok >= alloc) {
161 0 : alloc *= 2;
162 0 : buf = realloc(buf, alloc * sizeof(char*));
163 : }
164 :
165 0 : buf[*ntok] = strtok(NULL, SEP);
166 : }
167 0 : return buf;
168 : }
169 :
170 : /**
171 : @brief Parse and return an instruction from a line.
172 :
173 : Input line should have no preceding or trailing whitespace (see trim()).
174 : This function will not return on error - it will just fprintf() the error
175 : message and exit with an error code. This will change eventually.
176 : @param line Text to parse.
177 : @param lineno Line number (just used for error msg).
178 : */
179 0 : static Instr read_instr(char *line, int lineno)
180 : {
181 : // First, we're going to tokenize the string into a statically allocated
182 : // buffer. We know we don't need more than like TODO
183 : size_t ntok;
184 0 : char **tokens = tokenize(line, &ntok);
185 0 : Instr inst = {.code=0, .c=0, .s=0, .x=NULL, .y=NULL, .lastidx=0};
186 :
187 0 : if (strcmp(tokens[0], Opcodes[Char]) == 0) {
188 0 : if (ntok != 2) {
189 0 : fprintf(stderr, "line %d: require 2 tokens for char\n", lineno);
190 0 : exit(1);
191 : }
192 0 : inst.code = Char;
193 0 : inst.c = tokens[1][0];
194 0 : } else if (strcmp(tokens[0], Opcodes[Match]) == 0) {
195 0 : if (ntok != 1) {
196 0 : fprintf(stderr, "line %d: require 1 token for match\n", lineno);
197 0 : exit(1);
198 : }
199 0 : inst.code = Match;
200 0 : } else if (strcmp(tokens[0], Opcodes[Jump]) == 0) {
201 0 : if (ntok != 2) {
202 0 : fprintf(stderr, "line %d: require 2 tokens for jump\n", lineno);
203 0 : exit(1);
204 : }
205 0 : inst.code = Jump;
206 0 : inst.x = (Instr*)tokens[1];
207 0 : } else if (strcmp(tokens[0], Opcodes[Split]) == 0) {
208 0 : if (ntok != 3) {
209 0 : fprintf(stderr, "line %d: require 3 tokens for split\n", lineno);
210 0 : exit(1);
211 : }
212 0 : inst.code = Split;
213 0 : inst.x = (Instr*)tokens[1];
214 0 : inst.y = (Instr*)tokens[2];
215 0 : } else if (strcmp(tokens[0], Opcodes[Save]) == 0) {
216 0 : if (ntok != 2) {
217 0 : fprintf(stderr, "line %d: require 2 tokens for save\n", lineno);
218 0 : exit(1);
219 : }
220 0 : inst.code = Save;
221 0 : sscanf(tokens[1], "%zu", &inst.s);
222 0 : } else if (strcmp(tokens[0], Opcodes[Any]) == 0) {
223 0 : if (ntok != 1) {
224 0 : fprintf(stderr, "line %d: require 1 token for any\n", lineno);
225 0 : exit(1);
226 : }
227 0 : inst.code = Any;
228 0 : } else if (strcmp(tokens[0], Opcodes[ Range]) == 0 ||
229 0 : strcmp(tokens[0], Opcodes[NRange]) == 0) {
230 0 : if (ntok % 2 == 0) {
231 0 : fprintf(stderr, "line %d, require even number of character tokens\n",
232 : lineno);
233 0 : exit(1);
234 : }
235 0 : inst.code = (strcmp(tokens[0], Opcodes[Range]) == 0) ? Range : NRange;
236 0 : inst.s = (size_t) (ntok - 1) / 2;
237 0 : char *block = calloc(ntok - 1, sizeof(char));
238 0 : inst.x = (Instr*)block;
239 0 : for (size_t i = 0; i < ntok - 1; i++) {
240 0 : block[i] = string_to_char(tokens[i+1]);
241 : }
242 : } else {
243 0 : fprintf(stderr, "line %d: unknown opcode \"%s\"\n", lineno, tokens[0]);
244 : }
245 0 : return inst;
246 : }
247 :
248 : /**
249 : @brief Return the instruction index corresponding to a label.
250 : @param labels Array of labels
251 : @param lablindices Corresponding indices for the labels
252 : @param nlabels Number of label/index pairs in the arrays
253 : @param label Label to search for
254 : @param line Line number (for error messages)
255 : */
256 0 : static size_t gettarget(char **labels, size_t *labelindices, size_t nlabels,
257 : char *label, size_t line)
258 : {
259 0 : for (size_t i = 0; i < nlabels; i++) {
260 0 : if (strcmp(labels[i], label) == 0) {
261 0 : return labelindices[i];
262 : }
263 : }
264 0 : fprintf(stderr, "line %zu: label \"%s\" not found\n", line, label);
265 0 : exit(1);
266 : }
267 :
268 : /**
269 : @brief Return a block of instructions from some text code.
270 : @param str Code
271 : @param[out] ninstr Where to put the number of instructions
272 : */
273 0 : Regex reread(char *str)
274 : {
275 0 : size_t nlines = 1;
276 0 : Instr *rv = NULL;
277 :
278 : // Count newlines.
279 0 : for (size_t i = 0; str[i]; i++) {
280 0 : if (str[i] == '\n') {
281 0 : nlines++;
282 : }
283 : }
284 :
285 : // Create an array of lines.
286 0 : char **lines = calloc(nlines, sizeof(char*));
287 0 : size_t j = 0;
288 0 : lines[j++] = str;
289 0 : for (size_t i = 0; str[i]; i++) {
290 0 : if (str[i] == '\n') {
291 0 : str[i] = '\0';
292 0 : lines[j++] = str + i + 1;
293 : }
294 : }
295 :
296 : // Trim whitespace of each line, and categorize the lines.
297 0 : size_t nlabels = 0;
298 0 : size_t ncode = 0;
299 0 : linetype *types = calloc(nlines, sizeof(linetype));
300 0 : for (size_t i = 0; i < nlines; i++) {
301 : char last;
302 0 : lines[i] = trim(lines[i], &last);
303 0 : if (last == '\0') {
304 0 : types[i] = Blank;
305 0 : } else if (last == ':') {
306 0 : types[i] = Label;
307 0 : nlabels++;
308 : } else {
309 0 : types[i] = Code;
310 0 : ncode++;
311 : }
312 : }
313 :
314 : // Associate each label with the next line of code.
315 0 : char **labels = calloc(nlabels, sizeof(char *));
316 0 : size_t *labelindices = calloc(nlabels, sizeof(size_t));
317 0 : ssize_t codeidx = -1;
318 0 : size_t labelidx = 0;
319 0 : for (size_t i = 0; i < nlines; i++) {
320 0 : if (types[i] == Label) {
321 0 : size_t len = strlen(lines[i]);
322 0 : lines[i][len-1] = '\0'; // remove the colon, we don't want it
323 0 : labels[labelidx] = lines[i];
324 0 : labelindices[labelidx] = codeidx + 1;
325 0 : labelidx++;
326 0 : } else if (types[i] == Code) {
327 0 : codeidx++;
328 : }
329 : }
330 : // we'll assume that the labels are valid for now
331 :
332 0 : rv = calloc(ncode, sizeof(Instr));
333 0 : codeidx = 0;
334 0 : for (size_t i = 0; i < nlines; i++) {
335 0 : if (types[i] != Code) {
336 0 : continue;
337 : }
338 :
339 0 : rv[codeidx] = read_instr(lines[i], i+1);
340 :
341 : // lookup labels and point them correctly
342 0 : if (rv[codeidx].code == Jump || rv[codeidx].code == Split) {
343 0 : rv[codeidx].x = rv + gettarget(labels, labelindices, nlabels, (char*)rv[codeidx].x, i+1);
344 : }
345 0 : if (rv[codeidx].code == Split) {
346 0 : rv[codeidx].y = rv + gettarget(labels, labelindices, nlabels, (char*)rv[codeidx].y, i+1);
347 : }
348 :
349 0 : codeidx++;
350 : }
351 :
352 0 : free(types);
353 0 : free(lines);
354 0 : free(labels);
355 0 : free(labelindices);
356 0 : return (Regex){.n=codeidx, .i=rv};
357 : }
358 :
359 : /**
360 : @brief Read a program from a file.
361 : */
362 0 : Regex refread(FILE *f) {
363 0 : size_t alloc = 4096;
364 0 : char *buf = malloc(alloc);
365 0 : size_t start = 0;
366 : while (true) {
367 0 : start += fread(buf, 1, alloc - start, f);
368 0 : if (start == alloc) {
369 0 : alloc *= 2;
370 0 : buf = realloc(buf, alloc);
371 : } else {
372 0 : break;
373 : }
374 0 : }
375 :
376 0 : Regex rv = reread(buf);
377 0 : free(buf);
378 0 : return rv;
379 : }
380 :
381 : /**
382 : @brief Write a program to a file.
383 : */
384 0 : void rewrite(Regex r, FILE *f)
385 : {
386 0 : size_t *labels = calloc(r.n, sizeof(size_t));
387 :
388 : // Find every instruction that needs a label.
389 0 : for (size_t i = 0; i < r.n; i++) {
390 0 : if (r.i[i].code == Jump || r.i[i].code == Split) {
391 0 : labels[r.i[i].x - r.i] = 1;
392 : }
393 0 : if (r.i[i].code == Split) {
394 0 : labels[r.i[i].y - r.i] = 1;
395 : }
396 : }
397 :
398 0 : size_t l = 1;
399 0 : for (size_t i = 0; i < r.n; i++) {
400 0 : if (labels[i] > 0) {
401 0 : labels[i] = l++;
402 : }
403 : }
404 :
405 0 : for (size_t i = 0; i < r.n; i++) {
406 0 : if (labels[i] > 0) {
407 0 : fprintf(f, "L%zu:\n", labels[i]);
408 : }
409 0 : char *block = (char*) r.i[i].x;
410 0 : switch (r.i[i].code) {
411 : case Char:
412 0 : fprintf(f, " char %s\n", char_to_string(r.i[i].c));
413 0 : break;
414 : case Match:
415 0 : fprintf(f, " match\n");
416 0 : break;
417 : case Jump:
418 0 : fprintf(f, " jump L%zu\n", labels[r.i[i].x - r.i]);
419 0 : break;
420 : case Split:
421 0 : fprintf(f, " split L%zu L%zu\n", labels[r.i[i].x - r.i],
422 0 : labels[r.i[i].y - r.i]);
423 0 : break;
424 : case Save:
425 0 : fprintf(f, " save %zu\n", r.i[i].s);
426 0 : break;
427 : case Any:
428 0 : fprintf(f, " any\n");
429 0 : break;
430 : case NRange:
431 0 : fprintf(f, " nrange");
432 0 : for (size_t j = 0; j < r.i[i].s; j++) {
433 0 : fprintf(f, " %s", char_to_string(block[2*j]));
434 0 : fprintf(f, " %s", char_to_string(block[2*j + 1]));
435 : }
436 0 : fprintf(f, "\n");
437 0 : break;
438 : case Range:
439 0 : fprintf(f, " range");
440 0 : for (size_t j = 0; j < r.i[i].s; j++) {
441 0 : fprintf(f, " %s", char_to_string(block[2*j]));
442 0 : fprintf(f, " %s", char_to_string(block[2*j + 1]));
443 : }
444 0 : fprintf(f, "\n");
445 0 : break;
446 : }
447 : }
448 :
449 0 : free(labels);
450 0 : }
451 :
452 37 : void refree(Regex r)
453 : {
454 175 : for (size_t i = 0; i < r.n; i++) {
455 138 : if (r.i[i].code == Range || r.i[i].code == NRange) {
456 12 : free(r.i[i].x);
457 : }
458 : }
459 37 : free(r.i);
460 37 : }
|
