From a904b493a9f86a9cfcfff032255352b7050ef271 Mon Sep 17 00:00:00 2001 From: Michal Krol Date: Thu, 4 Mar 2004 13:07:52 +0000 Subject: Added missing Copyrights. --- src/mesa/shader/grammar.c | 5559 +++++++++++++++++++++++---------------------- 1 file changed, 2799 insertions(+), 2760 deletions(-) (limited to 'src/mesa/shader/grammar.c') diff --git a/src/mesa/shader/grammar.c b/src/mesa/shader/grammar.c index 96449784571..0ed347bad51 100644 --- a/src/mesa/shader/grammar.c +++ b/src/mesa/shader/grammar.c @@ -1,2760 +1,2799 @@ -#ifndef GRAMMAR_PORT_BUILD -#error Do not build this file directly, build your grammar_XXX.c instead, which includes this file -#endif - -/* - Last Modified: 2004-II-8 -*/ - -/* - INTRODUCTION - ------------ - - The task is to check the syntax of an input string. Input string is a stream of ASCII - characters terminated with a null-character ('\0'). Checking it using C language is - difficult and hard to implement without bugs. It is hard to maintain and make changes when - the syntax changes. - - This is because of a high redundancy of the C code. Large blocks of code are duplicated with - only small changes. Even use of macros does not solve the problem because macros cannot - erase the complexity of the problem. - - The resolution is to create a new language that will be highly oriented to our task. Once - we describe a particular syntax, we are done. We can then focus on the code that implements - the language. The size and complexity of it is relatively small than the code that directly - checks the syntax. - - First, we must implement our new language. Here, the language is implemented in C, but it - could also be implemented in any other language. The code is listed below. We must take - a good care that it is bug free. This is simple because the code is simple and clean. - - Next, we must describe the syntax of our new language in itself. Once created and checked - manually that it is correct, we can use it to check another scripts. - - Note that our new language loading code does not have to check the syntax. It is because we - assume that the script describing itself is correct, and other scripts can be syntactically - checked by the former script. The loading code must only do semantic checking which leads us to - simple resolving references. - - THE LANGUAGE - ------------ - - Here I will describe the syntax of the new language (further called "Synek"). It is mainly a - sequence of declarations terminated by a semicolon. The declaration consists of a symbol, - which is an identifier, and its definition. A definition is in turn a sequence of specifiers - connected with ".and" or ".or" operator. These operators cannot be mixed together in a one - definition. Specifier can be a symbol, string, character, character range or a special - keyword ".true" or ".false". - - On the very beginning of the script there is a declaration of a root symbol and is in the form: - .syntax ; - The must be on of the symbols in declaration sequence. The syntax is correct if - the root symbol evaluates to true. A symbol evaluates to true if the definition associated with - the symbol evaluates to true. Definition evaluation depends on the operator used to connect - specifiers in the definition. If ".and" operator is used, definition evaluates to true if and - only if all the specifiers evaluate to true. If ".or" operator is used, definition evalutes to - true if any of the specifiers evaluates to true. If definition contains only one specifier, - it is evaluated as if it was connected with ".true" keyword by ".and" operator. - - If specifier is a ".true" keyword, it always evaluates to true. - - If specifier is a ".false" keyword, it always evaluates to false. Specifier evaluates to false - when it does not evaluate to true. - - Character range specifier is in the form: - '' - '' - If specifier is a character range, it evaluates to true if character in the stream is greater - or equal to and less or equal to . In that situation - the stream pointer is advanced to point to next character in the stream. All C-style escape - sequences are supported although trigraph sequences are not. The comparisions are performed - on 8-bit unsigned integers. - - Character specifier is in the form: - '' - It evaluates to true if the following character range specifier evaluates to true: - '' - '' - - String specifier is in the form: - "" - Let N be the number of characters in . Let [i] designate i-th character in - . Then the string specifier evaluates to true if and only if for i in the range [0, N) - the following character specifier evaluates to true: - '[i]' - If [i] is a quotation mark, '[i]' is replaced with '\[i]'. - - Symbol specifier can be optionally preceded by a ".loop" keyword in the form: - .loop (1) - where is defined as follows: - ; (2) - Construction (1) is replaced by the following code: - - and declaration (2) is replaced by the following: - .or .true; - .and ; - ; - - ESCAPE SEQUENCES - ---------------- - - Synek supports all escape sequences in character specifiers. The mapping table is listed below. - All occurences of the characters in the first column are replaced with the corresponding - character in the second column. - - Escape sequence Represents - ------------------------------------------------------------------------------------------------ - \a Bell (alert) - \b Backspace - \f Formfeed - \n New line - \r Carriage return - \t Horizontal tab - \v Vertical tab - \' Single quotation mark - \" Double quotation mark - \\ Backslash - \? Literal question mark - \ooo ASCII character in octal notation - \xhhh ASCII character in hexadecimal notation - ------------------------------------------------------------------------------------------------ - - RAISING ERRORS - -------------- - - Any specifier can be followed by a special construction that is executed when the specifier - evaluates to false. The construction is in the form: - .error - is an identifier declared earlier by error text declaration. The declaration is - in the form: - .errtext "" - When specifier evaluates to false and this construction is present, parsing is stopped - immediately and is returned as a result of parsing. The error position is also - returned and it is meant as an offset from the beggining of the stream to the character that - was valid so far. Example: - - (**** syntax script ****) - - .syntax program; - .errtext MISSING_SEMICOLON "missing ';'" - program declaration .and .loop space .and ';' .error MISSING_SEMICOLON .and - .loop space .and '\0'; - declaration "declare" .and .loop space .and identifier; - space ' '; - - (**** sample code ****) - - declare foo , - - In the example above checking the sample code will result in error message "missing ';'" and - error position 12. The sample code is not correct. Note the presence of '\0' specifier to - assure that there is no code after semicolon - only spaces. - can optionally contain identifier surrounded by dollar signs $. In such a case, - the identifier and dollar signs are replaced by a string retrieved by invoking symbol with - the identifier name. The starting position is the error position. The lenght of the resulting - string is the position after invoking the symbol. - - PRODUCTION - ---------- - - Synek not only checks the syntax but it can also produce (emit) bytes associated with specifiers - that evaluate to true. That is, every specifier and optional error construction can be followed - by a number of emit constructions that are in the form: - .emit - can be a HEX number, identifier, a star * or a dollar $. HEX number is preceded by - 0x or 0X. If is an identifier, it must be earlier declared by emit code declaration - in the form: - .emtcode - - When given specifier evaluates to true, all emits associated with the specifier are output - in order they were declared. A star means that last-read character should be output instead - of constant value. Example: - - (**** syntax script ****) - - .syntax foobar; - .emtcode WORD_FOO 0x01 - .emtcode WORD_BAR 0x02 - foobar FOO .emit WORD_FOO .or BAR .emit WORD_BAR .or .true .emit 0x00; - FOO "foo" .and SPACE; - BAR "bar" .and SPACE; - SPACE ' ' .or '\0'; - - (**** sample text 1 ****) - - foo - - (**** sample text 2 ****) - - foobar - - For both samples the result will be one-element array. For first sample text it will be - value 1, for second - 0. Note that every text will be accepted because of presence of - .true as an alternative. - - Another example: - - (**** syntax script ****) - - .syntax declaration; - .emtcode VARIABLE 0x01 - declaration "declare" .and .loop space .and - identifier .emit VARIABLE .and (1) - .true .emit 0x00 .and (2) - .loop space .and ';'; - space ' ' .or '\t'; - identifier .loop id_char .emit *; (3) - id_char 'a'-'z' .or 'A'-'Z' .or '_'; - - (**** sample code ****) - - declare fubar; - - In specifier (1) symbol is followed by .emit VARIABLE. If it evaluates to - true, VARIABLE constant and then production of the symbol is output. Specifier (2) is used - to terminate the string with null to signal when the string ends. Specifier (3) outputs - all characters that make declared identifier. The result of sample code will be the - following array: - { 1, 'f', 'u', 'b', 'a', 'r', 0 } - - If .emit is followed by dollar $, it means that current position should be output. Current - position is a 32-bit unsigned integer distance from the very beginning of the parsed string to - first character consumed by the specifier associated with the .emit instruction. Current - position is stored in the output buffer in Little-Endian convention (the lowest byte comes - first). -*/ - -static void mem_free (void **); - -/* - internal error messages -*/ -static const byte *OUT_OF_MEMORY = (byte *) "internal error 1001: out of physical memory"; -static const byte *UNRESOLVED_REFERENCE = (byte *) "internal error 1002: unresolved reference '$'"; -static const byte *INVALID_GRAMMAR_ID = (byte *) "internal error 1003: invalid grammar object"; -static const byte *INVALID_REGISTER_NAME = (byte *) "internal error 1004: invalid register name: '$'"; - -static const byte *error_message = NULL; -static byte *error_param = NULL; /* this is inserted into error_message in place of $ */ -static int error_position = -1; - -static byte *unknown = (byte *) "???"; - -static void clear_last_error () -{ - /* reset error message */ - error_message = NULL; - - /* free error parameter - if error_param is a "???" don't free it - it's static */ - if (error_param != unknown) - mem_free ((void **) &error_param); - else - error_param = NULL; - - /* reset error position */ - error_position = -1; -} - -static void set_last_error (const byte *msg, byte *param, int pos) -{ - /* error message can only be set only once */ - if (error_message != NULL) - { - mem_free (¶m); - return; - } - - error_message = msg; - - if (param != NULL) - error_param = param; - else - error_param = unknown; - - error_position = pos; -} - -/* - memory management routines -*/ -static void *mem_alloc (size_t size) -{ - void *ptr = grammar_alloc_malloc (size); - if (ptr == NULL) - set_last_error (OUT_OF_MEMORY, NULL, -1); - return ptr; -} - -static void *mem_copy (void *dst, const void *src, size_t size) -{ - return grammar_memory_copy (dst, src, size); -} - -static void mem_free (void **ptr) -{ - grammar_alloc_free (*ptr); - *ptr = NULL; -} - -static void *mem_realloc (void *ptr, size_t old_size, size_t new_size) -{ - void *ptr2 = grammar_alloc_realloc (ptr, old_size, new_size); - if (ptr2 == NULL) - set_last_error (OUT_OF_MEMORY, NULL, -1); - return ptr2; -} - -static byte *str_copy_n (byte *dst, const byte *src, size_t max_len) -{ - return grammar_string_copy_n (dst, src, max_len); -} - -static byte *str_duplicate (const byte *str) -{ - byte *new_str = grammar_string_duplicate (str); - if (new_str == NULL) - set_last_error (OUT_OF_MEMORY, NULL, -1); - return new_str; -} - -static int str_equal (const byte *str1, const byte *str2) -{ - return grammar_string_compare (str1, str2) == 0; -} - -static int str_equal_n (const byte *str1, const byte *str2, unsigned int n) -{ - return grammar_string_compare_n (str1, str2, n) == 0; -} - -static unsigned int str_length (const byte *str) -{ - return grammar_string_length (str); -} - -/* - string to byte map typedef -*/ -typedef struct map_byte_ -{ - byte *key; - byte data; - struct map_byte_ *next; -} map_byte; - -static void map_byte_create (map_byte **ma) -{ - *ma = mem_alloc (sizeof (map_byte)); - if (*ma) - { - (**ma).key = NULL; - (**ma).data = '\0'; - (**ma).next = NULL; - } -} - -/* XXX unfold the recursion */ -static void map_byte_destroy (map_byte **ma) -{ - if (*ma) - { - map_byte_destroy (&(**ma).next); - mem_free ((void **) &(**ma).key); - mem_free ((void **) ma); - } -} - -static void map_byte_append (map_byte **ma, map_byte **nm) -{ - while (*ma) - ma = &(**ma).next; - *ma = *nm; -} - -/* - searches the map for the specified key, - returns pointer to the element with the specified key if it exists - returns NULL otherwise -*/ -map_byte *map_byte_locate (map_byte **ma, const byte *key) -{ - while (*ma) - { - if (str_equal ((**ma).key, key)) - return *ma; - - ma = &(**ma).next; - } - - set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); - return NULL; -} - -/* - searches the map for specified key, - if the key is matched, *data is filled with data associated with the key, - returns 0 if the key is matched, - returns 1 otherwise -*/ -static int map_byte_find (map_byte **ma, const byte *key, byte *data) -{ - map_byte *found = map_byte_locate (ma, key); - if (found != NULL) - { - *data = found->data; - - return 0; - } - - return 1; -} - -/* - regbyte context typedef - - Each regbyte consists of its name and a default value. These are static and created at - grammar script compile-time, for example the following line: - .regbyte vertex_blend 0x00 - adds a new regbyte named "vertex_blend" to the static list and initializes it to 0. - When the script is executed, this regbyte can be accessed by name for read and write. When a - particular regbyte is written, a new regbyte_ctx entry is added to the top of the regbyte_ctx - stack. The new entry contains information abot which regbyte it references and its new value. - When a given regbyte is accessed for read, the stack is searched top-down to find an - entry that references the regbyte. The first matching entry is used to return the current - value it holds. If no entry is found, the default value is returned. -*/ -typedef struct regbyte_ctx_ -{ - map_byte *m_regbyte; - byte m_current_value; - struct regbyte_ctx_ *m_prev; -} regbyte_ctx; - -static void regbyte_ctx_create (regbyte_ctx **re) -{ - *re = mem_alloc (sizeof (regbyte_ctx)); - if (*re) - { - (**re).m_regbyte = NULL; - (**re).m_prev = NULL; - } -} - -static void regbyte_ctx_destroy (regbyte_ctx **re) -{ - if (*re) - { - mem_free ((void **) re); - } -} - -static byte regbyte_ctx_extract (regbyte_ctx **re, map_byte *reg) -{ - /* first lookup in the register stack */ - while (*re != NULL) - { - if ((**re).m_regbyte == reg) - return (**re).m_current_value; - - re = &(**re).m_prev; - } - - /* if not found - return the default value */ - return reg->data; -} - -/* - emit type typedef -*/ -typedef enum emit_type_ -{ - et_byte, /* explicit number */ - et_stream, /* eaten character */ - et_position /* current position */ -} emit_type; - -/* - emit destination typedef -*/ -typedef enum emit_dest_ -{ - ed_output, /* write to the output buffer */ - ed_regbyte /* write a particular regbyte */ -} emit_dest; - -/* - emit typedef -*/ -typedef struct emit_ -{ - emit_dest m_emit_dest; - emit_type m_emit_type; /* ed_output */ - byte m_byte; /* et_byte */ - map_byte *m_regbyte; /* ed_regbyte */ - byte *m_regname; /* ed_regbyte - temporary */ - struct emit_ *m_next; -} emit; - -static void emit_create (emit **em) -{ - *em = mem_alloc (sizeof (emit)); - if (*em) - { - (**em).m_emit_dest = ed_output; - (**em).m_emit_type = et_byte; - (**em).m_byte = '\0'; - (**em).m_regbyte = NULL; - (**em).m_regname = NULL; - (**em).m_next = NULL; - } -} - -static void emit_destroy (emit **em) -{ - if (*em) - { - emit_destroy (&(**em).m_next); - mem_free ((void **) &(**em).m_regname); - mem_free ((void **) em); - } -} - -/* - error typedef -*/ -typedef struct error_ -{ - byte *m_text; - byte *m_token_name; - struct rule_ *m_token; -} error; - -static void error_create (error **er) -{ - *er = mem_alloc (sizeof (error)); - if (*er) - { - (**er).m_text = NULL; - (**er).m_token_name = NULL; - (**er).m_token = NULL; - } -} - -static void error_destroy (error **er) -{ - if (*er) - { - mem_free ((void **) &(**er).m_text); - mem_free ((void **) &(**er).m_token_name); - mem_free ((void **) er); - } -} - -struct dict_; -static byte *error_get_token (error *, struct dict_ *, const byte *, unsigned int); - -/* - condition operand type typedef -*/ -typedef enum cond_oper_type_ -{ - cot_byte, /* constant 8-bit unsigned integer */ - cot_regbyte /* pointer to byte register containing the current value */ -} cond_oper_type; - -/* - condition operand typedef -*/ -typedef struct cond_oper_ -{ - cond_oper_type m_type; - byte m_byte; /* cot_byte */ - map_byte *m_regbyte; /* cot_regbyte */ - byte *m_regname; /* cot_regbyte - temporary */ -} cond_oper; - -/* - condition type typedef -*/ -typedef enum cond_type_ -{ - ct_equal, - ct_not_equal -} cond_type; - -/* - condition typedef -*/ -typedef struct cond_ -{ - cond_type m_type; - cond_oper m_operands[2]; -} cond; - -static void cond_create (cond **co) -{ - *co = mem_alloc (sizeof (cond)); - if (*co) - { - (**co).m_operands[0].m_regname = NULL; - (**co).m_operands[1].m_regname = NULL; - } -} - -static void cond_destroy (cond **co) -{ - if (*co) - { - mem_free ((void **) &(**co).m_operands[0].m_regname); - mem_free ((void **) &(**co).m_operands[1].m_regname); - mem_free ((void **) co); - } -} - -/* - specifier type typedef -*/ -typedef enum spec_type_ -{ - st_false, - st_true, - st_byte, - st_byte_range, - st_string, - st_identifier, - st_identifier_loop, - st_debug -} spec_type; - -/* - specifier typedef -*/ -typedef struct spec_ -{ - spec_type m_spec_type; - byte m_byte[2]; /* st_byte, st_byte_range */ - byte *m_string; /* st_string */ - struct rule_ *m_rule; /* st_identifier, st_identifier_loop */ - emit *m_emits; - error *m_errtext; - cond *m_cond; - struct spec_ *m_next; -} spec; - -static void spec_create (spec **sp) -{ - *sp = mem_alloc (sizeof (spec)); - if (*sp) - { - (**sp).m_spec_type = st_false; - (**sp).m_byte[0] = '\0'; - (**sp).m_byte[1] = '\0'; - (**sp).m_string = NULL; - (**sp).m_rule = NULL; - (**sp).m_emits = NULL; - (**sp).m_errtext = NULL; - (**sp).m_cond = NULL; - (**sp).m_next = NULL; - } -} - -static void spec_destroy (spec **sp) -{ - if (*sp) - { - spec_destroy (&(**sp).m_next); - emit_destroy (&(**sp).m_emits); - error_destroy (&(**sp).m_errtext); - mem_free ((void **) &(**sp).m_string); - cond_destroy (&(**sp).m_cond); - mem_free ((void **) sp); - } -} - -static void spec_append (spec **sp, spec **ns) -{ - while (*sp) - sp = &(**sp).m_next; - *sp = *ns; -} - -/* - operator typedef -*/ -typedef enum oper_ -{ - op_none, - op_and, - op_or -} oper; - -/* - rule typedef -*/ -typedef struct rule_ -{ - oper m_oper; - spec *m_specs; - struct rule_ *m_next; -/* int m_referenced; */ /* for debugging purposes */ -} rule; - -static void rule_create (rule **ru) -{ - *ru = mem_alloc (sizeof (rule)); - if (*ru) - { - (**ru).m_oper = op_none; - (**ru).m_specs = NULL; - (**ru).m_next = NULL; -/* (**ru).m_referenced = 0; */ - } -} - -static void rule_destroy (rule **ru) -{ - if (*ru) - { - rule_destroy (&(**ru).m_next); - spec_destroy (&(**ru).m_specs); - mem_free ((void **) ru); - } -} - -static void rule_append (rule **ru, rule **nr) -{ - while (*ru) - ru = &(**ru).m_next; - *ru = *nr; -} - -/* - returns unique grammar id -*/ -static grammar next_valid_grammar_id () -{ - static grammar id = 0; - - return ++id; -} - -/* - dictionary typedef -*/ -typedef struct dict_ -{ - rule *m_rulez; - rule *m_syntax; - rule *m_string; - map_byte *m_regbytes; - grammar m_id; - struct dict_ *m_next; -} dict; - -static void dict_create (dict **di) -{ - *di = mem_alloc (sizeof (dict)); - if (*di) - { - (**di).m_rulez = NULL; - (**di).m_syntax = NULL; - (**di).m_string = NULL; - (**di).m_regbytes = NULL; - (**di).m_id = next_valid_grammar_id (); - (**di).m_next = NULL; - } -} - -static void dict_destroy (dict **di) -{ - if (*di) - { - rule_destroy (&(**di).m_rulez); - map_byte_destroy (&(**di).m_regbytes); - mem_free ((void **) di); - } -} - -static void dict_append (dict **di, dict **nd) -{ - while (*di) - di = &(**di).m_next; - *di = *nd; -} - -static void dict_find (dict **di, grammar key, dict **data) -{ - while (*di) - { - if ((**di).m_id == key) - { - *data = *di; - return; - } - - di = &(**di).m_next; - } - - *data = NULL; -} - -static dict *g_dicts = NULL; - -/* - byte array typedef - - XXX this class is going to be replaced by a faster one, soon -*/ -typedef struct barray_ -{ - byte *data; - unsigned int len; -} barray; - -static void barray_create (barray **ba) -{ - *ba = mem_alloc (sizeof (barray)); - if (*ba) - { - (**ba).data = NULL; - (**ba).len = 0; - } -} - -static void barray_destroy (barray **ba) -{ - if (*ba) - { - mem_free ((void **) &(**ba).data); - mem_free ((void **) ba); - } -} - -/* - reallocates byte array to requested size, - returns 0 on success, - returns 1 otherwise -*/ -static int barray_resize (barray **ba, unsigned int nlen) -{ - byte *new_pointer; - - if (nlen == 0) - { - mem_free ((void **) &(**ba).data); - (**ba).data = NULL; - (**ba).len = 0; - - return 0; - } - else - { - new_pointer = mem_realloc ((**ba).data, (**ba).len * sizeof (byte), nlen * sizeof (byte)); - if (new_pointer) - { - (**ba).data = new_pointer; - (**ba).len = nlen; - - return 0; - } - } - - return 1; -} - -/* - adds byte array pointed by *nb to the end of array pointed by *ba, - returns 0 on success, - returns 1 otherwise -*/ -static int barray_append (barray **ba, barray **nb) -{ - const unsigned int len = (**ba).len; - - if (barray_resize (ba, (**ba).len + (**nb).len)) - return 1; - - mem_copy ((**ba).data + len, (**nb).data, (**nb).len); - - return 0; -} - -/* - adds emit chain pointed by em to the end of array pointed by *ba, - returns 0 on success, - returns 1 otherwise -*/ -static int barray_push (barray **ba, emit *em, byte c, unsigned int pos, regbyte_ctx **rbc) -{ - emit *temp = em; - unsigned int count = 0; - - while (temp) - { - if (temp->m_emit_dest == ed_output) - if (temp->m_emit_type == et_position) - count += 4; /* position is a 32-bit unsigned integer */ - else - count++; - - temp = temp->m_next; - } - - if (barray_resize (ba, (**ba).len + count)) - return 1; - - while (em) - { - if (em->m_emit_dest == ed_output) - { - if (em->m_emit_type == et_byte) - (**ba).data[(**ba).len - count--] = em->m_byte; - else if (em->m_emit_type == et_stream) - (**ba).data[(**ba).len - count--] = c; - else // em->type == et_position - (**ba).data[(**ba).len - count--] = (byte) pos, - (**ba).data[(**ba).len - count--] = (byte) (pos >> 8), - (**ba).data[(**ba).len - count--] = (byte) (pos >> 16), - (**ba).data[(**ba).len - count--] = (byte) (pos >> 24); - } - else - { - regbyte_ctx *new_rbc; - regbyte_ctx_create (&new_rbc); - if (new_rbc == NULL) - return 1; - - new_rbc->m_prev = *rbc; - new_rbc->m_regbyte = em->m_regbyte; - *rbc = new_rbc; - - if (em->m_emit_type == et_byte) - new_rbc->m_current_value = em->m_byte; - else if (em->m_emit_type == et_stream) - new_rbc->m_current_value = c; - } - - em = em->m_next; - } - - return 0; -} - -/* - string to string map typedef -*/ -typedef struct map_str_ -{ - byte *key; - byte *data; - struct map_str_ *next; -} map_str; - -static void map_str_create (map_str **ma) -{ - *ma = mem_alloc (sizeof (map_str)); - if (*ma) - { - (**ma).key = NULL; - (**ma).data = NULL; - (**ma).next = NULL; - } -} - -static void map_str_destroy (map_str **ma) -{ - if (*ma) - { - map_str_destroy (&(**ma).next); - mem_free ((void **) &(**ma).key); - mem_free ((void **) &(**ma).data); - mem_free ((void **) ma); - } -} - -static void map_str_append (map_str **ma, map_str **nm) -{ - while (*ma) - ma = &(**ma).next; - *ma = *nm; -} - -/* - searches the map for specified key, - if the key is matched, *data is filled with data associated with the key, - returns 0 if the key is matched, - returns 1 otherwise -*/ -static int map_str_find (map_str **ma, const byte *key, byte **data) -{ - while (*ma) - { - if (str_equal ((**ma).key, key)) - { - *data = str_duplicate ((**ma).data); - if (*data == NULL) - return 1; - - return 0; - } - - ma = &(**ma).next; - } - - set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); - return 1; -} - -/* - string to rule map typedef -*/ -typedef struct map_rule_ -{ - byte *key; - rule *data; - struct map_rule_ *next; -} map_rule; - -static void map_rule_create (map_rule **ma) -{ - *ma = mem_alloc (sizeof (map_rule)); - if (*ma) - { - (**ma).key = NULL; - (**ma).data = NULL; - (**ma).next = NULL; - } -} - -static void map_rule_destroy (map_rule **ma) -{ - if (*ma) - { - map_rule_destroy (&(**ma).next); - mem_free ((void **) &(**ma).key); - mem_free ((void **) ma); - } -} - -static void map_rule_append (map_rule **ma, map_rule **nm) -{ - while (*ma) - ma = &(**ma).next; - *ma = *nm; -} - -/* - searches the map for specified key, - if the key is matched, *data is filled with data associated with the key, - returns 0 if the is matched, - returns 1 otherwise -*/ -static int map_rule_find (map_rule **ma, const byte *key, rule **data) -{ - while (*ma) - { - if (str_equal ((**ma).key, key)) - { - *data = (**ma).data; - - return 0; - } - - ma = &(**ma).next; - } - - set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); - return 1; -} - -/* - returns 1 if given character is a white space, - returns 0 otherwise -*/ -static int is_space (byte c) -{ - return c == ' ' || c == '\t' || c == '\n' || c == '\r'; -} - -/* - advances text pointer by 1 if character pointed by *text is a space, - returns 1 if a space has been eaten, - returns 0 otherwise -*/ -static int eat_space (const byte **text) -{ - if (is_space (**text)) - { - (*text)++; - - return 1; - } - - return 0; -} - -/* - returns 1 if text points to C-style comment start string "/*", - returns 0 otherwise -*/ -static int is_comment_start (const byte *text) -{ - return text[0] == '/' && text[1] == '*'; -} - -/* - advances text pointer to first character after C-style comment block - if any, - returns 1 if C-style comment block has been encountered and eaten, - returns 0 otherwise -*/ -static int eat_comment (const byte **text) -{ - if (is_comment_start (*text)) - { - /* *text points to comment block - skip two characters to enter comment body */ - *text += 2; - /* skip any character except consecutive '*' and '/' */ - while (!((*text)[0] == '*' && (*text)[1] == '/')) - (*text)++; - /* skip those two terminating characters */ - *text += 2; - - return 1; - } - - return 0; -} - -/* - advances text pointer to first character that is neither space nor C-style comment block -*/ -static void eat_spaces (const byte **text) -{ - while (eat_space (text) || eat_comment (text)) - ; -} - -/* - resizes string pointed by *ptr to successfully add character c to the end of the string, - returns 0 on success, - returns 1 otherwise -*/ -static int string_grow (byte **ptr, unsigned int *len, byte c) -{ - /* reallocate the string in 16-byte increments */ - if ((*len & 0x0F) == 0x0F || *ptr == NULL) - { - byte *tmp = mem_realloc (*ptr, ((*len + 1) & ~0x0F) * sizeof (byte), - ((*len + 1 + 0x10) & ~0x0F) * sizeof (byte)); - if (tmp == NULL) - return 1; - - *ptr = tmp; - } - - if (c) - { - /* append given character */ - (*ptr)[*len] = c; - (*len)++; - } - (*ptr)[*len] = '\0'; - - return 0; -} - -/* - returns 1 if given character is a valid identifier character a-z, A-Z, 0-9 or _ - returns 0 otherwise -*/ -static int is_identifier (byte c) -{ - return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'; -} - -/* - copies characters from *text to *id until non-identifier character is encountered, - assumes that *id points to NULL object - caller is responsible for later freeing the string, - text pointer is advanced to point past the copied identifier, - returns 0 if identifier was successfully copied, - returns 1 otherwise -*/ -static int get_identifier (const byte **text, byte **id) -{ - const byte *t = *text; - byte *p = NULL; - unsigned int len = 0; - - if (string_grow (&p, &len, '\0')) - return 1; - - /* loop while next character in buffer is valid for identifiers */ - while (is_identifier (*t)) - { - if (string_grow (&p, &len, *t++)) - { - mem_free ((void **) &p); - return 1; - } - } - - *text = t; - *id = p; - - return 0; -} - -/* - returns 1 if given character is HEX digit 0-9, A-F or a-f, - returns 0 otherwise -*/ -static int is_hex (byte c) -{ - return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f'); -} - -/* - returns value of passed character as if it was HEX digit -*/ -static unsigned int hex2dec (byte c) -{ - if (c >= '0' && c <= '9') - return c - '0'; - if (c >= 'A' && c <= 'F') - return c - 'A' + 10; - return c - 'a' + 10; -} - -/* - converts sequence of HEX digits pointed by *text until non-HEX digit is encountered, - advances text pointer past the converted sequence, - returns the converted value -*/ -static unsigned int hex_convert (const byte **text) -{ - unsigned int value = 0; - - while (is_hex (**text)) - { - value = value * 0x10 + hex2dec (**text); - (*text)++; - } - - return value; -} - -/* - returns 1 if given character is OCT digit 0-7, - returns 0 otherwise -*/ -static int is_oct (byte c) -{ - return c >= '0' && c <= '7'; -} - -/* - returns value of passed character as if it was OCT digit -*/ -static int oct2dec (byte c) -{ - return c - '0'; -} - -static byte get_escape_sequence (const byte **text) -{ - int value = 0; - - /* skip '\' character */ - (*text)++; - - switch (*(*text)++) - { - case '\'': - return '\''; - case '"': - return '\"'; - case '?': - return '\?'; - case '\\': - return '\\'; - case 'a': - return '\a'; - case 'b': - return '\b'; - case 'f': - return '\f'; - case 'n': - return '\n'; - case 'r': - return '\r'; - case 't': - return '\t'; - case 'v': - return '\v'; - case 'x': - return (byte) hex_convert (text); - } - - (*text)--; - if (is_oct (**text)) - { - value = oct2dec (*(*text)++); - if (is_oct (**text)) - { - value = value * 010 + oct2dec (*(*text)++); - if (is_oct (**text)) - value = value * 010 + oct2dec (*(*text)++); - } - } - - return (byte) value; -} - -/* - copies characters from *text to *str until " or ' character is encountered, - assumes that *str points to NULL object - caller is responsible for later freeing the string, - assumes that *text points to " or ' character that starts the string, - text pointer is advanced to point past the " or ' character, - returns 0 if string was successfully copied, - returns 1 otherwise -*/ -static int get_string (const byte **text, byte **str) -{ - const byte *t = *text; - byte *p = NULL; - unsigned int len = 0; - byte term_char; - - if (string_grow (&p, &len, '\0')) - return 1; - - /* read " or ' character that starts the string */ - term_char = *t++; - /* while next character is not the terminating character */ - while (*t && *t != term_char) - { - byte c; - - if (*t == '\\') - c = get_escape_sequence (&t); - else - c = *t++; - - if (string_grow (&p, &len, c)) - { - mem_free ((void **) &p); - return 1; - } - } - /* skip " or ' character that ends the string */ - t++; - - *text = t; - *str = p; - return 0; -} - -/* - gets emit code, the syntax is: ".emtcode" " " " " ("0x" | "0X") - assumes that *text already points to , - returns 0 if emit code is successfully read, - returns 1 otherwise -*/ -static int get_emtcode (const byte **text, map_byte **ma) -{ - const byte *t = *text; - map_byte *m = NULL; - - map_byte_create (&m); - if (m == NULL) - return 1; - - if (get_identifier (&t, &m->key)) - { - map_byte_destroy (&m); - return 1; - } - eat_spaces (&t); - - if (*t == '\'') - { - byte *c; - - if (get_string (&t, &c)) - { - map_byte_destroy (&m); - return 1; - } - - m->data = (byte) c[0]; - mem_free ((void **) &c); - } - else - { - /* skip HEX "0x" or "0X" prefix */ - t += 2; - m->data = (byte) hex_convert (&t); - } - - eat_spaces (&t); - - *text = t; - *ma = m; - return 0; -} - -/* - gets regbyte declaration, the syntax is: ".regbyte" " " " " ("0x" | "0X") - assumes that *text already points to , - returns 0 if regbyte is successfully read, - returns 1 otherwise -*/ -static int get_regbyte (const byte **text, map_byte **ma) -{ - return get_emtcode (text, ma); -} - -/* - returns 0 on success, - returns 1 otherwise -*/ -static int get_errtext (const byte **text, map_str **ma) -{ - const byte *t = *text; - map_str *m = NULL; - - map_str_create (&m); - if (m == NULL) - return 1; - - if (get_identifier (&t, &m->key)) - { - map_str_destroy (&m); - return 1; - } - eat_spaces (&t); - - if (get_string (&t, &m->data)) - { - map_str_destroy (&m); - return 1; - } - eat_spaces (&t); - - *text = t; - *ma = m; - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int get_error (const byte **text, error **er, map_str *maps) -{ - const byte *t = *text; - byte *temp = NULL; - - if (*t != '.') - return 0; - - t++; - if (get_identifier (&t, &temp)) - return 1; - eat_spaces (&t); - - if (!str_equal ((byte *) "error", temp)) - { - mem_free ((void **) &temp); - return 0; - } - - mem_free ((void **) &temp); - - error_create (er); - if (*er == NULL) - return 1; - - if (*t == '\"') - { - if (get_string (&t, &(**er).m_text)) - { - error_destroy (er); - return 1; - } - eat_spaces (&t); - } - else - { - if (get_identifier (&t, &temp)) - { - error_destroy (er); - return 1; - } - eat_spaces (&t); - - if (map_str_find (&maps, temp, &(**er).m_text)) - { - mem_free ((void **) &temp); - error_destroy (er); - return 1; - } - - mem_free ((void **) &temp); - } - - /* try to extract "token" from "...$token$..." */ - { - byte *processed = NULL; - unsigned int len = 0, i = 0; - - if (string_grow (&processed, &len, '\0')) - { - error_destroy (er); - return 1; - } - - while (i < str_length ((**er).m_text)) - { - /* check if the dollar sign is repeated - if so skip it */ - if ((**er).m_text[i] == '$' && (**er).m_text[i + 1] == '$') - { - if (string_grow (&processed, &len, '$')) - { - mem_free ((void **) &processed); - error_destroy (er); - return 1; - } - - i += 2; - } - else if ((**er).m_text[i] != '$') - { - if (string_grow (&processed, &len, (**er).m_text[i])) - { - mem_free ((void **) &processed); - error_destroy (er); - return 1; - } - - i++; - } - else - { - if (string_grow (&processed, &len, '$')) - { - mem_free ((void **) &processed); - error_destroy (er); - return 1; - } - - { - /* length of token being extracted */ - unsigned int tlen = 0; - - if (string_grow (&(**er).m_token_name, &tlen, '\0')) - { - mem_free ((void **) &processed); - error_destroy (er); - return 1; - } - - /* skip the dollar sign */ - i++; - - while ((**er).m_text[i] != '$') - { - if (string_grow (&(**er).m_token_name, &tlen, (**er).m_text[i])) - { - mem_free ((void **) &processed); - error_destroy (er); - return 1; - } - - i++; - } - - /* skip the dollar sign */ - i++; - } - } - } - - mem_free ((void **) &(**er).m_text); - (**er).m_text = processed; - } - - *text = t; - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int get_emits (const byte **text, emit **em, map_byte *mapb) -{ - const byte *t = *text; - byte *temp = NULL; - emit *e = NULL; - emit_dest dest; - - if (*t != '.') - return 0; - - t++; - if (get_identifier (&t, &temp)) - return 1; - eat_spaces (&t); - - /* .emit */ - if (str_equal ((byte *) "emit", temp)) - dest = ed_output; - /* .load */ - else if (str_equal ((byte *) "load", temp)) - dest = ed_regbyte; - else - { - mem_free ((void **) &temp); - return 0; - } - - mem_free ((void **) &temp); - - emit_create (&e); - if (e == NULL) - return 1; - - e->m_emit_dest = dest; - - if (dest == ed_regbyte) - { - if (get_identifier (&t, &e->m_regname)) - { - emit_destroy (&e); - return 1; - } - eat_spaces (&t); - } - - /* 0xNN */ - if (*t == '0') - { - t += 2; - e->m_byte = (byte) hex_convert (&t); - - e->m_emit_type = et_byte; - } - /* * */ - else if (*t == '*') - { - t++; - - e->m_emit_type = et_stream; - } - /* $ */ - else if (*t == '$') - { - t++; - - e->m_emit_type = et_position; - } - /* 'c' */ - else if (*t == '\'') - { - if (get_string (&t, &temp)) - { - emit_destroy (&e); - return 1; - } - e->m_byte = (byte) temp[0]; - - mem_free ((void **) &temp); - - e->m_emit_type = et_byte; - } - else - { - if (get_identifier (&t, &temp)) - { - emit_destroy (&e); - return 1; - } - - if (map_byte_find (&mapb, temp, &e->m_byte)) - { - mem_free ((void **) &temp); - emit_destroy (&e); - return 1; - } - - mem_free ((void **) &temp); - - e->m_emit_type = et_byte; - } - - eat_spaces (&t); - - if (get_emits (&t, &e->m_next, mapb)) - { - emit_destroy (&e); - return 1; - } - - *text = t; - *em = e; - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int get_spec (const byte **text, spec **sp, map_str *maps, map_byte *mapb) -{ - const byte *t = *text; - spec *s = NULL; - - spec_create (&s); - if (s == NULL) - return 1; - - /* first - read optional .if statement */ - if (*t == '.') - { - const byte *u = t; - byte *keyword = NULL; - - /* skip the dot */ - u++; - - if (get_identifier (&u, &keyword)) - { - spec_destroy (&s); - return 1; - } - - /* .if */ - if (str_equal ((byte *) "if", keyword)) - { - cond_create (&s->m_cond); - if (s->m_cond == NULL) - { - spec_destroy (&s); - return 1; - } - - /* skip the left paren */ - eat_spaces (&u); - u++; - - /* get the left operand */ - eat_spaces (&u); - if (get_identifier (&u, &s->m_cond->m_operands[0].m_regname)) - { - spec_destroy (&s); - return 1; - } - s->m_cond->m_operands[0].m_type = cot_regbyte; - - /* get the operator (!= or ==) */ - eat_spaces (&u); - if (*u == '!') - s->m_cond->m_type = ct_not_equal; - else - s->m_cond->m_type = ct_equal; - u += 2; - - /* skip the 0x prefix */ - eat_spaces (&u); - u += 2; - - /* get the right operand */ - s->m_cond->m_operands[1].m_byte = hex_convert (&u); - s->m_cond->m_operands[1].m_type = cot_byte; - - /* skip the right paren */ - eat_spaces (&u); - u++; - - eat_spaces (&u); - - t = u; - } - - mem_free ((void **) &keyword); - } - - if (*t == '\'') - { - byte *temp = NULL; - - if (get_string (&t, &temp)) - { - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - if (*t == '-') - { - byte *temp2 = NULL; - - /* skip the '-' character */ - t++; - eat_spaces (&t); - - if (get_string (&t, &temp2)) - { - mem_free ((void **) &temp); - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - s->m_spec_type = st_byte_range; - s->m_byte[0] = *temp; - s->m_byte[1] = *temp2; - - mem_free ((void **) &temp2); - } - else - { - s->m_spec_type = st_byte; - *s->m_byte = *temp; - } - - mem_free ((void **) &temp); - } - else if (*t == '"') - { - if (get_string (&t, &s->m_string)) - { - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - s->m_spec_type = st_string; - } - else if (*t == '.') - { - byte *keyword = NULL; - - /* skip the dot */ - t++; - - if (get_identifier (&t, &keyword)) - { - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - /* .true */ - if (str_equal ((byte *) "true", keyword)) - { - s->m_spec_type = st_true; - } - /* .false */ - else if (str_equal ((byte *) "false", keyword)) - { - s->m_spec_type = st_false; - } - /* .debug */ - else if (str_equal ((byte *) "debug", keyword)) - { - s->m_spec_type = st_debug; - } - /* .loop */ - else if (str_equal ((byte *) "loop", keyword)) - { - if (get_identifier (&t, &s->m_string)) - { - mem_free ((void **) &keyword); - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - s->m_spec_type = st_identifier_loop; - } - - mem_free ((void **) &keyword); - } - else - { - if (get_identifier (&t, &s->m_string)) - { - spec_destroy (&s); - return 1; - } - eat_spaces (&t); - - s->m_spec_type = st_identifier; - } - - if (get_error (&t, &s->m_errtext, maps)) - { - spec_destroy (&s); - return 1; - } - - if (get_emits (&t, &s->m_emits, mapb)) - { - spec_destroy (&s); - return 1; - } - - *text = t; - *sp = s; - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int get_rule (const byte **text, rule **ru, map_str *maps, map_byte *mapb) -{ - const byte *t = *text; - rule *r = NULL; - - rule_create (&r); - if (r == NULL) - return 1; - - if (get_spec (&t, &r->m_specs, maps, mapb)) - { - rule_destroy (&r); - return 1; - } - - while (*t != ';') - { - byte *op = NULL; - spec *sp = NULL; - - /* skip the dot that precedes "and" or "or" */ - t++; - - /* read "and" or "or" keyword */ - if (get_identifier (&t, &op)) - { - rule_destroy (&r); - return 1; - } - eat_spaces (&t); - - if (r->m_oper == op_none) - { - /* .and */ - if (str_equal ((byte *) "and", op)) - r->m_oper = op_and; - /* .or */ - else - r->m_oper = op_or; - } - - mem_free ((void **) &op); - - if (get_spec (&t, &sp, maps, mapb)) - { - rule_destroy (&r); - return 1; - } - - spec_append (&r->m_specs, &sp); - } - - /* skip the semicolon */ - t++; - eat_spaces (&t); - - *text = t; - *ru = r; - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int update_dependency (map_rule *mapr, byte *symbol, rule **ru) -{ - if (map_rule_find (&mapr, symbol, ru)) - return 1; - -/* (**ru).m_referenced = 1; */ - - return 0; -} - -/* - returns 0 on success, - returns 1 otherwise, -*/ -static int update_dependencies (dict *di, map_rule *mapr, byte **syntax_symbol, - byte **string_symbol, map_byte *regbytes) -{ - rule *rulez = di->m_rulez; - - /* update dependecies for the root and lexer symbols */ - if (update_dependency (mapr, *syntax_symbol, &di->m_syntax) || - (*string_symbol != NULL && update_dependency (mapr, *string_symbol, &di->m_string))) - return 1; - - mem_free ((void **) syntax_symbol); - mem_free ((void **) string_symbol); - - /* update dependecies for the rest of the rules */ - while (rulez) - { - spec *sp = rulez->m_specs; - - /* iterate through all the specifiers */ - while (sp) - { - /* update dependency for identifier */ - if (sp->m_spec_type == st_identifier || sp->m_spec_type == st_identifier_loop) - { - if (update_dependency (mapr, sp->m_string, &sp->m_rule)) - return 1; - - mem_free ((void **) &sp->m_string); - } - - /* some errtexts reference to a rule */ - if (sp->m_errtext && sp->m_errtext->m_token_name) - { - if (update_dependency (mapr, sp->m_errtext->m_token_name, &sp->m_errtext->m_token)) - return 1; - - mem_free ((void **) &sp->m_errtext->m_token_name); - } - - /* update dependency for condition */ - if (sp->m_cond) - { - int i; - for (i = 0; i < 2; i++) - if (sp->m_cond->m_operands[i].m_type == cot_regbyte) - { - sp->m_cond->m_operands[i].m_regbyte = map_byte_locate (®bytes, - sp->m_cond->m_operands[i].m_regname); - - if (sp->m_cond->m_operands[i].m_regbyte == NULL) - return 1; - - mem_free ((void **) &sp->m_cond->m_operands[i].m_regname); - } - } - - /* update dependency for all .load instructions */ - if (sp->m_emits) - { - emit *em = sp->m_emits; - while (em != NULL) - { - if (em->m_emit_dest == ed_regbyte) - { - em->m_regbyte = map_byte_locate (®bytes, em->m_regname); - - if (em->m_regbyte == NULL) - return 1; - - mem_free ((void **) &em->m_regname); - } - - em = em->m_next; - } - } - - sp = sp->m_next; - } - - rulez = rulez->m_next; - } - -/* check for unreferenced symbols */ -/* de = di->m_defntns; - while (de) - { - if (!de->m_referenced) - { - map_def *ma = mapd; - while (ma) - { - if (ma->data == de) - { - assert (0); - break; - } - ma = ma->next; - } - } - de = de->m_next; - } -*/ - return 0; -} - -static int satisfies_condition (cond *co, regbyte_ctx *ctx) -{ - byte values[2]; - int i; - - if (co == NULL) - return 1; - - for (i = 0; i < 2; i++) - switch (co->m_operands[i].m_type) - { - case cot_byte: - values[i] = co->m_operands[i].m_byte; - break; - case cot_regbyte: - values[i] = regbyte_ctx_extract (&ctx, co->m_operands[i].m_regbyte); - break; - } - - switch (co->m_type) - { - case ct_equal: - return values[0] == values[1]; - case ct_not_equal: - return values[0] != values[1]; - } - - return 0; -} - -static void free_regbyte_ctx_stack (regbyte_ctx *top, regbyte_ctx *limit) -{ - while (top != limit) - { - regbyte_ctx *rbc = top->m_prev; - regbyte_ctx_destroy (&top); - top = rbc; - } -} - -typedef enum match_result_ -{ - mr_not_matched, /* the examined string does not match */ - mr_matched, /* the examined string matches */ - mr_error_raised, /* mr_not_matched + error has been raised */ - mr_dont_emit, /* used by identifier loops only */ - mr_internal_error /* an internal error has occured such as out of memory */ -} match_result; - -/* - This function does the main job. It parses the text and generates output data. - - XXX optimize it - the barray seems to be the bottleneck -*/ -static match_result match (dict *di, const byte *text, unsigned int *index, rule *ru, barray **ba, - int filtering_string, regbyte_ctx **rbc) -{ - unsigned int ind = *index; - match_result status = mr_not_matched; - spec *sp = ru->m_specs; - regbyte_ctx *ctx = *rbc; - - /* for every specifier in the rule */ - while (sp) - { - unsigned int i, len, save_ind = ind; - barray *array = NULL; - - if (satisfies_condition (sp->m_cond, ctx)) - { - switch (sp->m_spec_type) - { - case st_identifier: - barray_create (&array); - if (array == NULL) - { - free_regbyte_ctx_stack (ctx, *rbc); - return mr_internal_error; - } - - status = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); - if (status == mr_internal_error) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - return mr_internal_error; - } - break; - case st_string: - len = str_length (sp->m_string); - - /* prefilter the stream */ - if (!filtering_string && di->m_string) - { - barray *ba; - unsigned int filter_index = 0; - match_result result; - regbyte_ctx *null_ctx = NULL; - - barray_create (&ba); - if (ba == NULL) - { - free_regbyte_ctx_stack (ctx, *rbc); - return mr_internal_error; - } - - result = match (di, text + ind, &filter_index, di->m_string, &ba, 1, &null_ctx); - - if (result == mr_internal_error) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&ba); - return mr_internal_error; - } - - if (result != mr_matched) - { - barray_destroy (&ba); - status = mr_not_matched; - break; - } - - barray_destroy (&ba); - - if (filter_index != len || !str_equal_n (sp->m_string, text + ind, len)) - { - status = mr_not_matched; - break; - } - - status = mr_matched; - ind += len; - } - else - { - status = mr_matched; - for (i = 0; status == mr_matched && i < len; i++) - if (text[ind + i] != sp->m_string[i]) - status = mr_not_matched; - if (status == mr_matched) - ind += len; - } - break; - case st_byte: - status = text[ind] == *sp->m_byte ? mr_matched : mr_not_matched; - if (status == mr_matched) - ind++; - break; - case st_byte_range: - status = (text[ind] >= sp->m_byte[0] && text[ind] <= sp->m_byte[1]) ? - mr_matched : mr_not_matched; - if (status == mr_matched) - ind++; - break; - case st_true: - status = mr_matched; - break; - case st_false: - status = mr_not_matched; - break; - case st_debug: - status = ru->m_oper == op_and ? mr_matched : mr_not_matched; - break; - case st_identifier_loop: - barray_create (&array); - if (array == NULL) - { - free_regbyte_ctx_stack (ctx, *rbc); - return mr_internal_error; - } - - status = mr_dont_emit; - for (;;) - { - match_result result; - - save_ind = ind; - result = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); - - if (result == mr_error_raised) - { - status = result; - break; - } - else if (result == mr_matched) - { - if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx) || - barray_append (ba, &array)) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - return mr_internal_error; - } - barray_destroy (&array); - barray_create (&array); - if (array == NULL) - { - free_regbyte_ctx_stack (ctx, *rbc); - return mr_internal_error; - } - } - else if (result == mr_internal_error) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - return mr_internal_error; - } - else - break; - } - break; - } - } - else - { - status = mr_not_matched; - } - - if (status == mr_error_raised) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - - return mr_error_raised; - } - - if (ru->m_oper == op_and && status != mr_matched && status != mr_dont_emit) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - - if (sp->m_errtext) - { - set_last_error (sp->m_errtext->m_text, error_get_token (sp->m_errtext, di, text, - ind), ind); - - return mr_error_raised; - } - - return mr_not_matched; - } - - if (status == mr_matched) - { - if (sp->m_emits) - if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx)) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - return mr_internal_error; - } - - if (array) - if (barray_append (ba, &array)) - { - free_regbyte_ctx_stack (ctx, *rbc); - barray_destroy (&array); - return mr_internal_error; - } - } - - barray_destroy (&array); - - /* if the rule operator is a logical or, we pick up the first matching specifier */ - if (ru->m_oper == op_or && (status == mr_matched || status == mr_dont_emit)) - { - *index = ind; - *rbc = ctx; - return mr_matched; - } - - sp = sp->m_next; - } - - /* everything went fine - all specifiers match up */ - if (ru->m_oper == op_and && (status == mr_matched || status == mr_dont_emit)) - { - *index = ind; - *rbc = ctx; - return mr_matched; - } - - free_regbyte_ctx_stack (ctx, *rbc); - return mr_not_matched; -} - -static byte *error_get_token (error *er, dict *di, const byte *text, unsigned int ind) -{ - byte *str = NULL; - - if (er->m_token) - { - barray *ba; - unsigned int filter_index = 0; - regbyte_ctx *ctx = NULL; - - barray_create (&ba); - if (ba != NULL) - { - if (match (di, text + ind, &filter_index, er->m_token, &ba, 0, &ctx) == mr_matched && - filter_index) - { - str = mem_alloc (filter_index + 1); - if (str != NULL) - { - str_copy_n (str, text + ind, filter_index); - str[filter_index] = '\0'; - } - } - barray_destroy (&ba); - } - } - - return str; -} - -typedef struct grammar_load_state_ -{ - dict *di; - byte *syntax_symbol; - byte *string_symbol; - map_str *maps; - map_byte *mapb; - map_rule *mapr; -} grammar_load_state; - -static void grammar_load_state_create (grammar_load_state **gr) -{ - *gr = mem_alloc (sizeof (grammar_load_state)); - if (*gr) - { - (**gr).di = NULL; - (**gr).syntax_symbol = NULL; - (**gr).string_symbol = NULL; - (**gr).maps = NULL; - (**gr).mapb = NULL; - (**gr).mapr = NULL; - } -} - -static void grammar_load_state_destroy (grammar_load_state **gr) -{ - if (*gr) - { - dict_destroy (&(**gr).di); - mem_free ((void **) &(**gr).syntax_symbol); - mem_free ((void **) &(**gr).string_symbol); - map_str_destroy (&(**gr).maps); - map_byte_destroy (&(**gr).mapb); - map_rule_destroy (&(**gr).mapr); - mem_free ((void **) gr); - } -} - -/* - the API -*/ - -grammar grammar_load_from_text (const byte *text) -{ - grammar_load_state *g = NULL; - grammar id = 0; - - clear_last_error (); - - grammar_load_state_create (&g); - if (g == NULL) - return 0; - - dict_create (&g->di); - if (g->di == NULL) - { - grammar_load_state_destroy (&g); - return 0; - } - - eat_spaces (&text); - - /* skip ".syntax" keyword */ - text += 7; - eat_spaces (&text); - - /* retrieve root symbol */ - if (get_identifier (&text, &g->syntax_symbol)) - { - grammar_load_state_destroy (&g); - return 0; - } - eat_spaces (&text); - - /* skip semicolon */ - text++; - eat_spaces (&text); - - while (*text) - { - byte *symbol = NULL; - int is_dot = *text == '.'; - - if (is_dot) - text++; - - if (get_identifier (&text, &symbol)) - { - grammar_load_state_destroy (&g); - return 0; - } - eat_spaces (&text); - - /* .emtcode */ - if (is_dot && str_equal (symbol, (byte *) "emtcode")) - { - map_byte *ma = NULL; - - mem_free ((void **) &symbol); - - if (get_emtcode (&text, &ma)) - { - grammar_load_state_destroy (&g); - return 0; - } - - map_byte_append (&g->mapb, &ma); - } - /* .regbyte */ - else if (is_dot && str_equal (symbol, (byte *) "regbyte")) - { - map_byte *ma = NULL; - - mem_free ((void **) &symbol); - - if (get_regbyte (&text, &ma)) - { - grammar_load_state_destroy (&g); - return 0; - } - - map_byte_append (&g->di->m_regbytes, &ma); - } - /* .errtext */ - else if (is_dot && str_equal (symbol, (byte *) "errtext")) - { - map_str *ma = NULL; - - mem_free ((void **) &symbol); - - if (get_errtext (&text, &ma)) - { - grammar_load_state_destroy (&g); - return 0; - } - - map_str_append (&g->maps, &ma); - } - /* .string */ - else if (is_dot && str_equal (symbol, (byte *) "string")) - { - mem_free ((void **) &symbol); - - if (g->di->m_string != NULL) - { - grammar_load_state_destroy (&g); - return 0; - } - - if (get_identifier (&text, &g->string_symbol)) - { - grammar_load_state_destroy (&g); - return 0; - } - - /* skip semicolon */ - eat_spaces (&text); - text++; - eat_spaces (&text); - } - else - { - rule *ru = NULL; - map_rule *ma = NULL; - - if (get_rule (&text, &ru, g->maps, g->mapb)) - { - grammar_load_state_destroy (&g); - return 0; - } - - rule_append (&g->di->m_rulez, &ru); - - /* if a rule consist of only one specifier, give it an ".and" operator */ - if (ru->m_oper == op_none) - ru->m_oper = op_and; - - map_rule_create (&ma); - if (ma == NULL) - { - grammar_load_state_destroy (&g); - return 0; - } - - ma->key = symbol; - ma->data = ru; - map_rule_append (&g->mapr, &ma); - } - } - - if (update_dependencies (g->di, g->mapr, &g->syntax_symbol, &g->string_symbol, - g->di->m_regbytes)) - { - grammar_load_state_destroy (&g); - return 0; - } - - dict_append (&g_dicts, &g->di); - id = g->di->m_id; - g->di = NULL; - - grammar_load_state_destroy (&g); - - return id; -} - -int grammar_set_reg8 (grammar id, const byte *name, byte value) -{ - dict *di = NULL; - map_byte *reg = NULL; - - clear_last_error (); - - dict_find (&g_dicts, id, &di); - if (di == NULL) - { - set_last_error (INVALID_GRAMMAR_ID, NULL, -1); - return 0; - } - - reg = map_byte_locate (&di->m_regbytes, name); - if (reg == NULL) - { - set_last_error (INVALID_REGISTER_NAME, str_duplicate (name), -1); - return 0; - } - - reg->data = value; - return 1; -} - -int grammar_check (grammar id, const byte *text, byte **prod, unsigned int *size) -{ - dict *di = NULL; - barray *ba = NULL; - unsigned int index = 0; - regbyte_ctx *rbc = NULL; - - clear_last_error (); - - dict_find (&g_dicts, id, &di); - if (di == NULL) - { - set_last_error (INVALID_GRAMMAR_ID, NULL, -1); - return 0; - } - - barray_create (&ba); - if (ba == NULL) - return 0; - - *prod = NULL; - *size = 0; - - if (match (di, text, &index, di->m_syntax, &ba, 0, &rbc) != mr_matched) - { - barray_destroy (&ba); - free_regbyte_ctx_stack (rbc, NULL); - return 0; - } - - free_regbyte_ctx_stack (rbc, NULL); - - *prod = mem_alloc (ba->len * sizeof (byte)); - if (*prod == NULL) - { - barray_destroy (&ba); - return 0; - } - - mem_copy (*prod, ba->data, ba->len * sizeof (byte)); - *size = ba->len; - barray_destroy (&ba); - - return 1; -} - -int grammar_destroy (grammar id) -{ - dict **di = &g_dicts; - - clear_last_error (); - - while (*di != NULL) - { - if ((**di).m_id == id) - { - dict *tmp = *di; - *di = (**di).m_next; - dict_destroy (&tmp); - return 1; - } - - di = &(**di).m_next; - } - - set_last_error (INVALID_GRAMMAR_ID, NULL, -1); - return 0; -} - -void grammar_get_last_error (byte *text, unsigned int size, int *pos) -{ - unsigned int len = 0, dots_made = 0; - const byte *p = error_message; - - *text = '\0'; - -#define APPEND_CHARACTER(x) if (dots_made == 0) {\ - if (len < size - 1) {\ - text[len++] = (x); text[len] = '\0';\ - } else {\ - int i;\ - for (i = 0; i < 3; i++)\ - if (--len >= 0)\ - text[len] = '.';\ - dots_made = 1;\ - }\ - } - - if (p) - while (*p) - if (*p == '$') - { - const byte *r = error_param; - - while (*r) - { - APPEND_CHARACTER(*r) - r++; - } - - p++; - } - else - { - APPEND_CHARACTER(*p) - p++; - } - - *pos = error_position; - -#undef APPEND_CHARACTER - -} - +/* + * Mesa 3-D graphics library + * Version: 6.1 + * + * Copyright (C) 1999-2004 Brian Paul All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * \file grammar.c + * syntax parsing engine + * \author Michal Krol + */ + +#ifndef GRAMMAR_PORT_BUILD +#error Do not build this file directly, build your grammar_XXX.c instead, which includes this file +#endif + +/* + Last Modified: 2004-II-8 +*/ + +/* + INTRODUCTION + ------------ + + The task is to check the syntax of an input string. Input string is a stream of ASCII + characters terminated with a null-character ('\0'). Checking it using C language is + difficult and hard to implement without bugs. It is hard to maintain and make changes when + the syntax changes. + + This is because of a high redundancy of the C code. Large blocks of code are duplicated with + only small changes. Even use of macros does not solve the problem because macros cannot + erase the complexity of the problem. + + The resolution is to create a new language that will be highly oriented to our task. Once + we describe a particular syntax, we are done. We can then focus on the code that implements + the language. The size and complexity of it is relatively small than the code that directly + checks the syntax. + + First, we must implement our new language. Here, the language is implemented in C, but it + could also be implemented in any other language. The code is listed below. We must take + a good care that it is bug free. This is simple because the code is simple and clean. + + Next, we must describe the syntax of our new language in itself. Once created and checked + manually that it is correct, we can use it to check another scripts. + + Note that our new language loading code does not have to check the syntax. It is because we + assume that the script describing itself is correct, and other scripts can be syntactically + checked by the former script. The loading code must only do semantic checking which leads us to + simple resolving references. + + THE LANGUAGE + ------------ + + Here I will describe the syntax of the new language (further called "Synek"). It is mainly a + sequence of declarations terminated by a semicolon. The declaration consists of a symbol, + which is an identifier, and its definition. A definition is in turn a sequence of specifiers + connected with ".and" or ".or" operator. These operators cannot be mixed together in a one + definition. Specifier can be a symbol, string, character, character range or a special + keyword ".true" or ".false". + + On the very beginning of the script there is a declaration of a root symbol and is in the form: + .syntax ; + The must be on of the symbols in declaration sequence. The syntax is correct if + the root symbol evaluates to true. A symbol evaluates to true if the definition associated with + the symbol evaluates to true. Definition evaluation depends on the operator used to connect + specifiers in the definition. If ".and" operator is used, definition evaluates to true if and + only if all the specifiers evaluate to true. If ".or" operator is used, definition evalutes to + true if any of the specifiers evaluates to true. If definition contains only one specifier, + it is evaluated as if it was connected with ".true" keyword by ".and" operator. + + If specifier is a ".true" keyword, it always evaluates to true. + + If specifier is a ".false" keyword, it always evaluates to false. Specifier evaluates to false + when it does not evaluate to true. + + Character range specifier is in the form: + '' - '' + If specifier is a character range, it evaluates to true if character in the stream is greater + or equal to and less or equal to . In that situation + the stream pointer is advanced to point to next character in the stream. All C-style escape + sequences are supported although trigraph sequences are not. The comparisions are performed + on 8-bit unsigned integers. + + Character specifier is in the form: + '' + It evaluates to true if the following character range specifier evaluates to true: + '' - '' + + String specifier is in the form: + "" + Let N be the number of characters in . Let [i] designate i-th character in + . Then the string specifier evaluates to true if and only if for i in the range [0, N) + the following character specifier evaluates to true: + '[i]' + If [i] is a quotation mark, '[i]' is replaced with '\[i]'. + + Symbol specifier can be optionally preceded by a ".loop" keyword in the form: + .loop (1) + where is defined as follows: + ; (2) + Construction (1) is replaced by the following code: + + and declaration (2) is replaced by the following: + .or .true; + .and ; + ; + + Synek supports also a register mechanizm. User can, in its SYN file, declare a number of + registers that can be accessed in the syn body. Each reg has its name and a default value. + The register is one byte wide. The C code can change the default value by calling + grammar_set_reg8() with grammar id, register name and a new value. As we know, each rule is + a sequence of specifiers joined with .and or .or operator. And now each specifier can be + prefixed with a condition expression in a form ".if ( )" + where can be == or !=. If the condition evaluates to false, the specifier + evaluates to .false. Otherwise it evalutes to the specifier. + + ESCAPE SEQUENCES + ---------------- + + Synek supports all escape sequences in character specifiers. The mapping table is listed below. + All occurences of the characters in the first column are replaced with the corresponding + character in the second column. + + Escape sequence Represents + ------------------------------------------------------------------------------------------------ + \a Bell (alert) + \b Backspace + \f Formfeed + \n New line + \r Carriage return + \t Horizontal tab + \v Vertical tab + \' Single quotation mark + \" Double quotation mark + \\ Backslash + \? Literal question mark + \ooo ASCII character in octal notation + \xhhh ASCII character in hexadecimal notation + ------------------------------------------------------------------------------------------------ + + RAISING ERRORS + -------------- + + Any specifier can be followed by a special construction that is executed when the specifier + evaluates to false. The construction is in the form: + .error + is an identifier declared earlier by error text declaration. The declaration is + in the form: + .errtext "" + When specifier evaluates to false and this construction is present, parsing is stopped + immediately and is returned as a result of parsing. The error position is also + returned and it is meant as an offset from the beggining of the stream to the character that + was valid so far. Example: + + (**** syntax script ****) + + .syntax program; + .errtext MISSING_SEMICOLON "missing ';'" + program declaration .and .loop space .and ';' .error MISSING_SEMICOLON .and + .loop space .and '\0'; + declaration "declare" .and .loop space .and identifier; + space ' '; + + (**** sample code ****) + + declare foo , + + In the example above checking the sample code will result in error message "missing ';'" and + error position 12. The sample code is not correct. Note the presence of '\0' specifier to + assure that there is no code after semicolon - only spaces. + can optionally contain identifier surrounded by dollar signs $. In such a case, + the identifier and dollar signs are replaced by a string retrieved by invoking symbol with + the identifier name. The starting position is the error position. The lenght of the resulting + string is the position after invoking the symbol. + + PRODUCTION + ---------- + + Synek not only checks the syntax but it can also produce (emit) bytes associated with specifiers + that evaluate to true. That is, every specifier and optional error construction can be followed + by a number of emit constructions that are in the form: + .emit + can be a HEX number, identifier, a star * or a dollar $. HEX number is preceded by + 0x or 0X. If is an identifier, it must be earlier declared by emit code declaration + in the form: + .emtcode + + When given specifier evaluates to true, all emits associated with the specifier are output + in order they were declared. A star means that last-read character should be output instead + of constant value. Example: + + (**** syntax script ****) + + .syntax foobar; + .emtcode WORD_FOO 0x01 + .emtcode WORD_BAR 0x02 + foobar FOO .emit WORD_FOO .or BAR .emit WORD_BAR .or .true .emit 0x00; + FOO "foo" .and SPACE; + BAR "bar" .and SPACE; + SPACE ' ' .or '\0'; + + (**** sample text 1 ****) + + foo + + (**** sample text 2 ****) + + foobar + + For both samples the result will be one-element array. For first sample text it will be + value 1, for second - 0. Note that every text will be accepted because of presence of + .true as an alternative. + + Another example: + + (**** syntax script ****) + + .syntax declaration; + .emtcode VARIABLE 0x01 + declaration "declare" .and .loop space .and + identifier .emit VARIABLE .and (1) + .true .emit 0x00 .and (2) + .loop space .and ';'; + space ' ' .or '\t'; + identifier .loop id_char .emit *; (3) + id_char 'a'-'z' .or 'A'-'Z' .or '_'; + + (**** sample code ****) + + declare fubar; + + In specifier (1) symbol is followed by .emit VARIABLE. If it evaluates to + true, VARIABLE constant and then production of the symbol is output. Specifier (2) is used + to terminate the string with null to signal when the string ends. Specifier (3) outputs + all characters that make declared identifier. The result of sample code will be the + following array: + { 1, 'f', 'u', 'b', 'a', 'r', 0 } + + If .emit is followed by dollar $, it means that current position should be output. Current + position is a 32-bit unsigned integer distance from the very beginning of the parsed string to + first character consumed by the specifier associated with the .emit instruction. Current + position is stored in the output buffer in Little-Endian convention (the lowest byte comes + first). +*/ + +static void mem_free (void **); + +/* + internal error messages +*/ +static const byte *OUT_OF_MEMORY = (byte *) "internal error 1001: out of physical memory"; +static const byte *UNRESOLVED_REFERENCE = (byte *) "internal error 1002: unresolved reference '$'"; +static const byte *INVALID_GRAMMAR_ID = (byte *) "internal error 1003: invalid grammar object"; +static const byte *INVALID_REGISTER_NAME = (byte *) "internal error 1004: invalid register name: '$'"; + +static const byte *error_message = NULL; +static byte *error_param = NULL; /* this is inserted into error_message in place of $ */ +static int error_position = -1; + +static byte *unknown = (byte *) "???"; + +static void clear_last_error () +{ + /* reset error message */ + error_message = NULL; + + /* free error parameter - if error_param is a "???" don't free it - it's static */ + if (error_param != unknown) + mem_free ((void **) &error_param); + else + error_param = NULL; + + /* reset error position */ + error_position = -1; +} + +static void set_last_error (const byte *msg, byte *param, int pos) +{ + /* error message can only be set only once */ + if (error_message != NULL) + { + mem_free (¶m); + return; + } + + error_message = msg; + + if (param != NULL) + error_param = param; + else + error_param = unknown; + + error_position = pos; +} + +/* + memory management routines +*/ +static void *mem_alloc (size_t size) +{ + void *ptr = grammar_alloc_malloc (size); + if (ptr == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return ptr; +} + +static void *mem_copy (void *dst, const void *src, size_t size) +{ + return grammar_memory_copy (dst, src, size); +} + +static void mem_free (void **ptr) +{ + grammar_alloc_free (*ptr); + *ptr = NULL; +} + +static void *mem_realloc (void *ptr, size_t old_size, size_t new_size) +{ + void *ptr2 = grammar_alloc_realloc (ptr, old_size, new_size); + if (ptr2 == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return ptr2; +} + +static byte *str_copy_n (byte *dst, const byte *src, size_t max_len) +{ + return grammar_string_copy_n (dst, src, max_len); +} + +static byte *str_duplicate (const byte *str) +{ + byte *new_str = grammar_string_duplicate (str); + if (new_str == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return new_str; +} + +static int str_equal (const byte *str1, const byte *str2) +{ + return grammar_string_compare (str1, str2) == 0; +} + +static int str_equal_n (const byte *str1, const byte *str2, unsigned int n) +{ + return grammar_string_compare_n (str1, str2, n) == 0; +} + +static unsigned int str_length (const byte *str) +{ + return grammar_string_length (str); +} + +/* + string to byte map typedef +*/ +typedef struct map_byte_ +{ + byte *key; + byte data; + struct map_byte_ *next; +} map_byte; + +static void map_byte_create (map_byte **ma) +{ + *ma = mem_alloc (sizeof (map_byte)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = '\0'; + (**ma).next = NULL; + } +} + +/* XXX unfold the recursion */ +static void map_byte_destroy (map_byte **ma) +{ + if (*ma) + { + map_byte_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) ma); + } +} + +static void map_byte_append (map_byte **ma, map_byte **nm) +{ + while (*ma) + ma = &(**ma).next; + *ma = *nm; +} + +/* + searches the map for the specified key, + returns pointer to the element with the specified key if it exists + returns NULL otherwise +*/ +map_byte *map_byte_locate (map_byte **ma, const byte *key) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + return *ma; + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return NULL; +} + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the key is matched, + returns 1 otherwise +*/ +static int map_byte_find (map_byte **ma, const byte *key, byte *data) +{ + map_byte *found = map_byte_locate (ma, key); + if (found != NULL) + { + *data = found->data; + + return 0; + } + + return 1; +} + +/* + regbyte context typedef + + Each regbyte consists of its name and a default value. These are static and created at + grammar script compile-time, for example the following line: + .regbyte vertex_blend 0x00 + adds a new regbyte named "vertex_blend" to the static list and initializes it to 0. + When the script is executed, this regbyte can be accessed by name for read and write. When a + particular regbyte is written, a new regbyte_ctx entry is added to the top of the regbyte_ctx + stack. The new entry contains information abot which regbyte it references and its new value. + When a given regbyte is accessed for read, the stack is searched top-down to find an + entry that references the regbyte. The first matching entry is used to return the current + value it holds. If no entry is found, the default value is returned. +*/ +typedef struct regbyte_ctx_ +{ + map_byte *m_regbyte; + byte m_current_value; + struct regbyte_ctx_ *m_prev; +} regbyte_ctx; + +static void regbyte_ctx_create (regbyte_ctx **re) +{ + *re = mem_alloc (sizeof (regbyte_ctx)); + if (*re) + { + (**re).m_regbyte = NULL; + (**re).m_prev = NULL; + } +} + +static void regbyte_ctx_destroy (regbyte_ctx **re) +{ + if (*re) + { + mem_free ((void **) re); + } +} + +static byte regbyte_ctx_extract (regbyte_ctx **re, map_byte *reg) +{ + /* first lookup in the register stack */ + while (*re != NULL) + { + if ((**re).m_regbyte == reg) + return (**re).m_current_value; + + re = &(**re).m_prev; + } + + /* if not found - return the default value */ + return reg->data; +} + +/* + emit type typedef +*/ +typedef enum emit_type_ +{ + et_byte, /* explicit number */ + et_stream, /* eaten character */ + et_position /* current position */ +} emit_type; + +/* + emit destination typedef +*/ +typedef enum emit_dest_ +{ + ed_output, /* write to the output buffer */ + ed_regbyte /* write a particular regbyte */ +} emit_dest; + +/* + emit typedef +*/ +typedef struct emit_ +{ + emit_dest m_emit_dest; + emit_type m_emit_type; /* ed_output */ + byte m_byte; /* et_byte */ + map_byte *m_regbyte; /* ed_regbyte */ + byte *m_regname; /* ed_regbyte - temporary */ + struct emit_ *m_next; +} emit; + +static void emit_create (emit **em) +{ + *em = mem_alloc (sizeof (emit)); + if (*em) + { + (**em).m_emit_dest = ed_output; + (**em).m_emit_type = et_byte; + (**em).m_byte = '\0'; + (**em).m_regbyte = NULL; + (**em).m_regname = NULL; + (**em).m_next = NULL; + } +} + +static void emit_destroy (emit **em) +{ + if (*em) + { + emit_destroy (&(**em).m_next); + mem_free ((void **) &(**em).m_regname); + mem_free ((void **) em); + } +} + +/* + error typedef +*/ +typedef struct error_ +{ + byte *m_text; + byte *m_token_name; + struct rule_ *m_token; +} error; + +static void error_create (error **er) +{ + *er = mem_alloc (sizeof (error)); + if (*er) + { + (**er).m_text = NULL; + (**er).m_token_name = NULL; + (**er).m_token = NULL; + } +} + +static void error_destroy (error **er) +{ + if (*er) + { + mem_free ((void **) &(**er).m_text); + mem_free ((void **) &(**er).m_token_name); + mem_free ((void **) er); + } +} + +struct dict_; +static byte *error_get_token (error *, struct dict_ *, const byte *, unsigned int); + +/* + condition operand type typedef +*/ +typedef enum cond_oper_type_ +{ + cot_byte, /* constant 8-bit unsigned integer */ + cot_regbyte /* pointer to byte register containing the current value */ +} cond_oper_type; + +/* + condition operand typedef +*/ +typedef struct cond_oper_ +{ + cond_oper_type m_type; + byte m_byte; /* cot_byte */ + map_byte *m_regbyte; /* cot_regbyte */ + byte *m_regname; /* cot_regbyte - temporary */ +} cond_oper; + +/* + condition type typedef +*/ +typedef enum cond_type_ +{ + ct_equal, + ct_not_equal +} cond_type; + +/* + condition typedef +*/ +typedef struct cond_ +{ + cond_type m_type; + cond_oper m_operands[2]; +} cond; + +static void cond_create (cond **co) +{ + *co = mem_alloc (sizeof (cond)); + if (*co) + { + (**co).m_operands[0].m_regname = NULL; + (**co).m_operands[1].m_regname = NULL; + } +} + +static void cond_destroy (cond **co) +{ + if (*co) + { + mem_free ((void **) &(**co).m_operands[0].m_regname); + mem_free ((void **) &(**co).m_operands[1].m_regname); + mem_free ((void **) co); + } +} + +/* + specifier type typedef +*/ +typedef enum spec_type_ +{ + st_false, + st_true, + st_byte, + st_byte_range, + st_string, + st_identifier, + st_identifier_loop, + st_debug +} spec_type; + +/* + specifier typedef +*/ +typedef struct spec_ +{ + spec_type m_spec_type; + byte m_byte[2]; /* st_byte, st_byte_range */ + byte *m_string; /* st_string */ + struct rule_ *m_rule; /* st_identifier, st_identifier_loop */ + emit *m_emits; + error *m_errtext; + cond *m_cond; + struct spec_ *m_next; +} spec; + +static void spec_create (spec **sp) +{ + *sp = mem_alloc (sizeof (spec)); + if (*sp) + { + (**sp).m_spec_type = st_false; + (**sp).m_byte[0] = '\0'; + (**sp).m_byte[1] = '\0'; + (**sp).m_string = NULL; + (**sp).m_rule = NULL; + (**sp).m_emits = NULL; + (**sp).m_errtext = NULL; + (**sp).m_cond = NULL; + (**sp).m_next = NULL; + } +} + +static void spec_destroy (spec **sp) +{ + if (*sp) + { + spec_destroy (&(**sp).m_next); + emit_destroy (&(**sp).m_emits); + error_destroy (&(**sp).m_errtext); + mem_free ((void **) &(**sp).m_string); + cond_destroy (&(**sp).m_cond); + mem_free ((void **) sp); + } +} + +static void spec_append (spec **sp, spec **ns) +{ + while (*sp) + sp = &(**sp).m_next; + *sp = *ns; +} + +/* + operator typedef +*/ +typedef enum oper_ +{ + op_none, + op_and, + op_or +} oper; + +/* + rule typedef +*/ +typedef struct rule_ +{ + oper m_oper; + spec *m_specs; + struct rule_ *m_next; +/* int m_referenced; */ /* for debugging purposes */ +} rule; + +static void rule_create (rule **ru) +{ + *ru = mem_alloc (sizeof (rule)); + if (*ru) + { + (**ru).m_oper = op_none; + (**ru).m_specs = NULL; + (**ru).m_next = NULL; +/* (**ru).m_referenced = 0; */ + } +} + +static void rule_destroy (rule **ru) +{ + if (*ru) + { + rule_destroy (&(**ru).m_next); + spec_destroy (&(**ru).m_specs); + mem_free ((void **) ru); + } +} + +static void rule_append (rule **ru, rule **nr) +{ + while (*ru) + ru = &(**ru).m_next; + *ru = *nr; +} + +/* + returns unique grammar id +*/ +static grammar next_valid_grammar_id () +{ + static grammar id = 0; + + return ++id; +} + +/* + dictionary typedef +*/ +typedef struct dict_ +{ + rule *m_rulez; + rule *m_syntax; + rule *m_string; + map_byte *m_regbytes; + grammar m_id; + struct dict_ *m_next; +} dict; + +static void dict_create (dict **di) +{ + *di = mem_alloc (sizeof (dict)); + if (*di) + { + (**di).m_rulez = NULL; + (**di).m_syntax = NULL; + (**di).m_string = NULL; + (**di).m_regbytes = NULL; + (**di).m_id = next_valid_grammar_id (); + (**di).m_next = NULL; + } +} + +static void dict_destroy (dict **di) +{ + if (*di) + { + rule_destroy (&(**di).m_rulez); + map_byte_destroy (&(**di).m_regbytes); + mem_free ((void **) di); + } +} + +static void dict_append (dict **di, dict **nd) +{ + while (*di) + di = &(**di).m_next; + *di = *nd; +} + +static void dict_find (dict **di, grammar key, dict **data) +{ + while (*di) + { + if ((**di).m_id == key) + { + *data = *di; + return; + } + + di = &(**di).m_next; + } + + *data = NULL; +} + +static dict *g_dicts = NULL; + +/* + byte array typedef + + XXX this class is going to be replaced by a faster one, soon +*/ +typedef struct barray_ +{ + byte *data; + unsigned int len; +} barray; + +static void barray_create (barray **ba) +{ + *ba = mem_alloc (sizeof (barray)); + if (*ba) + { + (**ba).data = NULL; + (**ba).len = 0; + } +} + +static void barray_destroy (barray **ba) +{ + if (*ba) + { + mem_free ((void **) &(**ba).data); + mem_free ((void **) ba); + } +} + +/* + reallocates byte array to requested size, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_resize (barray **ba, unsigned int nlen) +{ + byte *new_pointer; + + if (nlen == 0) + { + mem_free ((void **) &(**ba).data); + (**ba).data = NULL; + (**ba).len = 0; + + return 0; + } + else + { + new_pointer = mem_realloc ((**ba).data, (**ba).len * sizeof (byte), nlen * sizeof (byte)); + if (new_pointer) + { + (**ba).data = new_pointer; + (**ba).len = nlen; + + return 0; + } + } + + return 1; +} + +/* + adds byte array pointed by *nb to the end of array pointed by *ba, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_append (barray **ba, barray **nb) +{ + const unsigned int len = (**ba).len; + + if (barray_resize (ba, (**ba).len + (**nb).len)) + return 1; + + mem_copy ((**ba).data + len, (**nb).data, (**nb).len); + + return 0; +} + +/* + adds emit chain pointed by em to the end of array pointed by *ba, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_push (barray **ba, emit *em, byte c, unsigned int pos, regbyte_ctx **rbc) +{ + emit *temp = em; + unsigned int count = 0; + + while (temp) + { + if (temp->m_emit_dest == ed_output) + if (temp->m_emit_type == et_position) + count += 4; /* position is a 32-bit unsigned integer */ + else + count++; + + temp = temp->m_next; + } + + if (barray_resize (ba, (**ba).len + count)) + return 1; + + while (em) + { + if (em->m_emit_dest == ed_output) + { + if (em->m_emit_type == et_byte) + (**ba).data[(**ba).len - count--] = em->m_byte; + else if (em->m_emit_type == et_stream) + (**ba).data[(**ba).len - count--] = c; + else // em->type == et_position + (**ba).data[(**ba).len - count--] = (byte) pos, + (**ba).data[(**ba).len - count--] = (byte) (pos >> 8), + (**ba).data[(**ba).len - count--] = (byte) (pos >> 16), + (**ba).data[(**ba).len - count--] = (byte) (pos >> 24); + } + else + { + regbyte_ctx *new_rbc; + regbyte_ctx_create (&new_rbc); + if (new_rbc == NULL) + return 1; + + new_rbc->m_prev = *rbc; + new_rbc->m_regbyte = em->m_regbyte; + *rbc = new_rbc; + + if (em->m_emit_type == et_byte) + new_rbc->m_current_value = em->m_byte; + else if (em->m_emit_type == et_stream) + new_rbc->m_current_value = c; + } + + em = em->m_next; + } + + return 0; +} + +/* + string to string map typedef +*/ +typedef struct map_str_ +{ + byte *key; + byte *data; + struct map_str_ *next; +} map_str; + +static void map_str_create (map_str **ma) +{ + *ma = mem_alloc (sizeof (map_str)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = NULL; + (**ma).next = NULL; + } +} + +static void map_str_destroy (map_str **ma) +{ + if (*ma) + { + map_str_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) &(**ma).data); + mem_free ((void **) ma); + } +} + +static void map_str_append (map_str **ma, map_str **nm) +{ + while (*ma) + ma = &(**ma).next; + *ma = *nm; +} + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the key is matched, + returns 1 otherwise +*/ +static int map_str_find (map_str **ma, const byte *key, byte **data) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + { + *data = str_duplicate ((**ma).data); + if (*data == NULL) + return 1; + + return 0; + } + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return 1; +} + +/* + string to rule map typedef +*/ +typedef struct map_rule_ +{ + byte *key; + rule *data; + struct map_rule_ *next; +} map_rule; + +static void map_rule_create (map_rule **ma) +{ + *ma = mem_alloc (sizeof (map_rule)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = NULL; + (**ma).next = NULL; + } +} + +static void map_rule_destroy (map_rule **ma) +{ + if (*ma) + { + map_rule_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) ma); + } +} + +static void map_rule_append (map_rule **ma, map_rule **nm) +{ + while (*ma) + ma = &(**ma).next; + *ma = *nm; +} + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the is matched, + returns 1 otherwise +*/ +static int map_rule_find (map_rule **ma, const byte *key, rule **data) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + { + *data = (**ma).data; + + return 0; + } + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return 1; +} + +/* + returns 1 if given character is a white space, + returns 0 otherwise +*/ +static int is_space (byte c) +{ + return c == ' ' || c == '\t' || c == '\n' || c == '\r'; +} + +/* + advances text pointer by 1 if character pointed by *text is a space, + returns 1 if a space has been eaten, + returns 0 otherwise +*/ +static int eat_space (const byte **text) +{ + if (is_space (**text)) + { + (*text)++; + + return 1; + } + + return 0; +} + +/* + returns 1 if text points to C-style comment start string "/*", + returns 0 otherwise +*/ +static int is_comment_start (const byte *text) +{ + return text[0] == '/' && text[1] == '*'; +} + +/* + advances text pointer to first character after C-style comment block - if any, + returns 1 if C-style comment block has been encountered and eaten, + returns 0 otherwise +*/ +static int eat_comment (const byte **text) +{ + if (is_comment_start (*text)) + { + /* *text points to comment block - skip two characters to enter comment body */ + *text += 2; + /* skip any character except consecutive '*' and '/' */ + while (!((*text)[0] == '*' && (*text)[1] == '/')) + (*text)++; + /* skip those two terminating characters */ + *text += 2; + + return 1; + } + + return 0; +} + +/* + advances text pointer to first character that is neither space nor C-style comment block +*/ +static void eat_spaces (const byte **text) +{ + while (eat_space (text) || eat_comment (text)) + ; +} + +/* + resizes string pointed by *ptr to successfully add character c to the end of the string, + returns 0 on success, + returns 1 otherwise +*/ +static int string_grow (byte **ptr, unsigned int *len, byte c) +{ + /* reallocate the string in 16-byte increments */ + if ((*len & 0x0F) == 0x0F || *ptr == NULL) + { + byte *tmp = mem_realloc (*ptr, ((*len + 1) & ~0x0F) * sizeof (byte), + ((*len + 1 + 0x10) & ~0x0F) * sizeof (byte)); + if (tmp == NULL) + return 1; + + *ptr = tmp; + } + + if (c) + { + /* append given character */ + (*ptr)[*len] = c; + (*len)++; + } + (*ptr)[*len] = '\0'; + + return 0; +} + +/* + returns 1 if given character is a valid identifier character a-z, A-Z, 0-9 or _ + returns 0 otherwise +*/ +static int is_identifier (byte c) +{ + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'; +} + +/* + copies characters from *text to *id until non-identifier character is encountered, + assumes that *id points to NULL object - caller is responsible for later freeing the string, + text pointer is advanced to point past the copied identifier, + returns 0 if identifier was successfully copied, + returns 1 otherwise +*/ +static int get_identifier (const byte **text, byte **id) +{ + const byte *t = *text; + byte *p = NULL; + unsigned int len = 0; + + if (string_grow (&p, &len, '\0')) + return 1; + + /* loop while next character in buffer is valid for identifiers */ + while (is_identifier (*t)) + { + if (string_grow (&p, &len, *t++)) + { + mem_free ((void **) &p); + return 1; + } + } + + *text = t; + *id = p; + + return 0; +} + +/* + returns 1 if given character is HEX digit 0-9, A-F or a-f, + returns 0 otherwise +*/ +static int is_hex (byte c) +{ + return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f'); +} + +/* + returns value of passed character as if it was HEX digit +*/ +static unsigned int hex2dec (byte c) +{ + if (c >= '0' && c <= '9') + return c - '0'; + if (c >= 'A' && c <= 'F') + return c - 'A' + 10; + return c - 'a' + 10; +} + +/* + converts sequence of HEX digits pointed by *text until non-HEX digit is encountered, + advances text pointer past the converted sequence, + returns the converted value +*/ +static unsigned int hex_convert (const byte **text) +{ + unsigned int value = 0; + + while (is_hex (**text)) + { + value = value * 0x10 + hex2dec (**text); + (*text)++; + } + + return value; +} + +/* + returns 1 if given character is OCT digit 0-7, + returns 0 otherwise +*/ +static int is_oct (byte c) +{ + return c >= '0' && c <= '7'; +} + +/* + returns value of passed character as if it was OCT digit +*/ +static int oct2dec (byte c) +{ + return c - '0'; +} + +static byte get_escape_sequence (const byte **text) +{ + int value = 0; + + /* skip '\' character */ + (*text)++; + + switch (*(*text)++) + { + case '\'': + return '\''; + case '"': + return '\"'; + case '?': + return '\?'; + case '\\': + return '\\'; + case 'a': + return '\a'; + case 'b': + return '\b'; + case 'f': + return '\f'; + case 'n': + return '\n'; + case 'r': + return '\r'; + case 't': + return '\t'; + case 'v': + return '\v'; + case 'x': + return (byte) hex_convert (text); + } + + (*text)--; + if (is_oct (**text)) + { + value = oct2dec (*(*text)++); + if (is_oct (**text)) + { + value = value * 010 + oct2dec (*(*text)++); + if (is_oct (**text)) + value = value * 010 + oct2dec (*(*text)++); + } + } + + return (byte) value; +} + +/* + copies characters from *text to *str until " or ' character is encountered, + assumes that *str points to NULL object - caller is responsible for later freeing the string, + assumes that *text points to " or ' character that starts the string, + text pointer is advanced to point past the " or ' character, + returns 0 if string was successfully copied, + returns 1 otherwise +*/ +static int get_string (const byte **text, byte **str) +{ + const byte *t = *text; + byte *p = NULL; + unsigned int len = 0; + byte term_char; + + if (string_grow (&p, &len, '\0')) + return 1; + + /* read " or ' character that starts the string */ + term_char = *t++; + /* while next character is not the terminating character */ + while (*t && *t != term_char) + { + byte c; + + if (*t == '\\') + c = get_escape_sequence (&t); + else + c = *t++; + + if (string_grow (&p, &len, c)) + { + mem_free ((void **) &p); + return 1; + } + } + /* skip " or ' character that ends the string */ + t++; + + *text = t; + *str = p; + return 0; +} + +/* + gets emit code, the syntax is: ".emtcode" " " " " ("0x" | "0X") + assumes that *text already points to , + returns 0 if emit code is successfully read, + returns 1 otherwise +*/ +static int get_emtcode (const byte **text, map_byte **ma) +{ + const byte *t = *text; + map_byte *m = NULL; + + map_byte_create (&m); + if (m == NULL) + return 1; + + if (get_identifier (&t, &m->key)) + { + map_byte_destroy (&m); + return 1; + } + eat_spaces (&t); + + if (*t == '\'') + { + byte *c; + + if (get_string (&t, &c)) + { + map_byte_destroy (&m); + return 1; + } + + m->data = (byte) c[0]; + mem_free ((void **) &c); + } + else + { + /* skip HEX "0x" or "0X" prefix */ + t += 2; + m->data = (byte) hex_convert (&t); + } + + eat_spaces (&t); + + *text = t; + *ma = m; + return 0; +} + +/* + gets regbyte declaration, the syntax is: ".regbyte" " " " " ("0x" | "0X") + assumes that *text already points to , + returns 0 if regbyte is successfully read, + returns 1 otherwise +*/ +static int get_regbyte (const byte **text, map_byte **ma) +{ + return get_emtcode (text, ma); +} + +/* + returns 0 on success, + returns 1 otherwise +*/ +static int get_errtext (const byte **text, map_str **ma) +{ + const byte *t = *text; + map_str *m = NULL; + + map_str_create (&m); + if (m == NULL) + return 1; + + if (get_identifier (&t, &m->key)) + { + map_str_destroy (&m); + return 1; + } + eat_spaces (&t); + + if (get_string (&t, &m->data)) + { + map_str_destroy (&m); + return 1; + } + eat_spaces (&t); + + *text = t; + *ma = m; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_error (const byte **text, error **er, map_str *maps) +{ + const byte *t = *text; + byte *temp = NULL; + + if (*t != '.') + return 0; + + t++; + if (get_identifier (&t, &temp)) + return 1; + eat_spaces (&t); + + if (!str_equal ((byte *) "error", temp)) + { + mem_free ((void **) &temp); + return 0; + } + + mem_free ((void **) &temp); + + error_create (er); + if (*er == NULL) + return 1; + + if (*t == '\"') + { + if (get_string (&t, &(**er).m_text)) + { + error_destroy (er); + return 1; + } + eat_spaces (&t); + } + else + { + if (get_identifier (&t, &temp)) + { + error_destroy (er); + return 1; + } + eat_spaces (&t); + + if (map_str_find (&maps, temp, &(**er).m_text)) + { + mem_free ((void **) &temp); + error_destroy (er); + return 1; + } + + mem_free ((void **) &temp); + } + + /* try to extract "token" from "...$token$..." */ + { + byte *processed = NULL; + unsigned int len = 0, i = 0; + + if (string_grow (&processed, &len, '\0')) + { + error_destroy (er); + return 1; + } + + while (i < str_length ((**er).m_text)) + { + /* check if the dollar sign is repeated - if so skip it */ + if ((**er).m_text[i] == '$' && (**er).m_text[i + 1] == '$') + { + if (string_grow (&processed, &len, '$')) + { + mem_free ((void **) &processed); + error_destroy (er); + return 1; + } + + i += 2; + } + else if ((**er).m_text[i] != '$') + { + if (string_grow (&processed, &len, (**er).m_text[i])) + { + mem_free ((void **) &processed); + error_destroy (er); + return 1; + } + + i++; + } + else + { + if (string_grow (&processed, &len, '$')) + { + mem_free ((void **) &processed); + error_destroy (er); + return 1; + } + + { + /* length of token being extracted */ + unsigned int tlen = 0; + + if (string_grow (&(**er).m_token_name, &tlen, '\0')) + { + mem_free ((void **) &processed); + error_destroy (er); + return 1; + } + + /* skip the dollar sign */ + i++; + + while ((**er).m_text[i] != '$') + { + if (string_grow (&(**er).m_token_name, &tlen, (**er).m_text[i])) + { + mem_free ((void **) &processed); + error_destroy (er); + return 1; + } + + i++; + } + + /* skip the dollar sign */ + i++; + } + } + } + + mem_free ((void **) &(**er).m_text); + (**er).m_text = processed; + } + + *text = t; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_emits (const byte **text, emit **em, map_byte *mapb) +{ + const byte *t = *text; + byte *temp = NULL; + emit *e = NULL; + emit_dest dest; + + if (*t != '.') + return 0; + + t++; + if (get_identifier (&t, &temp)) + return 1; + eat_spaces (&t); + + /* .emit */ + if (str_equal ((byte *) "emit", temp)) + dest = ed_output; + /* .load */ + else if (str_equal ((byte *) "load", temp)) + dest = ed_regbyte; + else + { + mem_free ((void **) &temp); + return 0; + } + + mem_free ((void **) &temp); + + emit_create (&e); + if (e == NULL) + return 1; + + e->m_emit_dest = dest; + + if (dest == ed_regbyte) + { + if (get_identifier (&t, &e->m_regname)) + { + emit_destroy (&e); + return 1; + } + eat_spaces (&t); + } + + /* 0xNN */ + if (*t == '0') + { + t += 2; + e->m_byte = (byte) hex_convert (&t); + + e->m_emit_type = et_byte; + } + /* * */ + else if (*t == '*') + { + t++; + + e->m_emit_type = et_stream; + } + /* $ */ + else if (*t == '$') + { + t++; + + e->m_emit_type = et_position; + } + /* 'c' */ + else if (*t == '\'') + { + if (get_string (&t, &temp)) + { + emit_destroy (&e); + return 1; + } + e->m_byte = (byte) temp[0]; + + mem_free ((void **) &temp); + + e->m_emit_type = et_byte; + } + else + { + if (get_identifier (&t, &temp)) + { + emit_destroy (&e); + return 1; + } + + if (map_byte_find (&mapb, temp, &e->m_byte)) + { + mem_free ((void **) &temp); + emit_destroy (&e); + return 1; + } + + mem_free ((void **) &temp); + + e->m_emit_type = et_byte; + } + + eat_spaces (&t); + + if (get_emits (&t, &e->m_next, mapb)) + { + emit_destroy (&e); + return 1; + } + + *text = t; + *em = e; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_spec (const byte **text, spec **sp, map_str *maps, map_byte *mapb) +{ + const byte *t = *text; + spec *s = NULL; + + spec_create (&s); + if (s == NULL) + return 1; + + /* first - read optional .if statement */ + if (*t == '.') + { + const byte *u = t; + byte *keyword = NULL; + + /* skip the dot */ + u++; + + if (get_identifier (&u, &keyword)) + { + spec_destroy (&s); + return 1; + } + + /* .if */ + if (str_equal ((byte *) "if", keyword)) + { + cond_create (&s->m_cond); + if (s->m_cond == NULL) + { + spec_destroy (&s); + return 1; + } + + /* skip the left paren */ + eat_spaces (&u); + u++; + + /* get the left operand */ + eat_spaces (&u); + if (get_identifier (&u, &s->m_cond->m_operands[0].m_regname)) + { + spec_destroy (&s); + return 1; + } + s->m_cond->m_operands[0].m_type = cot_regbyte; + + /* get the operator (!= or ==) */ + eat_spaces (&u); + if (*u == '!') + s->m_cond->m_type = ct_not_equal; + else + s->m_cond->m_type = ct_equal; + u += 2; + + /* skip the 0x prefix */ + eat_spaces (&u); + u += 2; + + /* get the right operand */ + s->m_cond->m_operands[1].m_byte = hex_convert (&u); + s->m_cond->m_operands[1].m_type = cot_byte; + + /* skip the right paren */ + eat_spaces (&u); + u++; + + eat_spaces (&u); + + t = u; + } + + mem_free ((void **) &keyword); + } + + if (*t == '\'') + { + byte *temp = NULL; + + if (get_string (&t, &temp)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + if (*t == '-') + { + byte *temp2 = NULL; + + /* skip the '-' character */ + t++; + eat_spaces (&t); + + if (get_string (&t, &temp2)) + { + mem_free ((void **) &temp); + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_byte_range; + s->m_byte[0] = *temp; + s->m_byte[1] = *temp2; + + mem_free ((void **) &temp2); + } + else + { + s->m_spec_type = st_byte; + *s->m_byte = *temp; + } + + mem_free ((void **) &temp); + } + else if (*t == '"') + { + if (get_string (&t, &s->m_string)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_string; + } + else if (*t == '.') + { + byte *keyword = NULL; + + /* skip the dot */ + t++; + + if (get_identifier (&t, &keyword)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + /* .true */ + if (str_equal ((byte *) "true", keyword)) + { + s->m_spec_type = st_true; + } + /* .false */ + else if (str_equal ((byte *) "false", keyword)) + { + s->m_spec_type = st_false; + } + /* .debug */ + else if (str_equal ((byte *) "debug", keyword)) + { + s->m_spec_type = st_debug; + } + /* .loop */ + else if (str_equal ((byte *) "loop", keyword)) + { + if (get_identifier (&t, &s->m_string)) + { + mem_free ((void **) &keyword); + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_identifier_loop; + } + + mem_free ((void **) &keyword); + } + else + { + if (get_identifier (&t, &s->m_string)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_identifier; + } + + if (get_error (&t, &s->m_errtext, maps)) + { + spec_destroy (&s); + return 1; + } + + if (get_emits (&t, &s->m_emits, mapb)) + { + spec_destroy (&s); + return 1; + } + + *text = t; + *sp = s; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_rule (const byte **text, rule **ru, map_str *maps, map_byte *mapb) +{ + const byte *t = *text; + rule *r = NULL; + + rule_create (&r); + if (r == NULL) + return 1; + + if (get_spec (&t, &r->m_specs, maps, mapb)) + { + rule_destroy (&r); + return 1; + } + + while (*t != ';') + { + byte *op = NULL; + spec *sp = NULL; + + /* skip the dot that precedes "and" or "or" */ + t++; + + /* read "and" or "or" keyword */ + if (get_identifier (&t, &op)) + { + rule_destroy (&r); + return 1; + } + eat_spaces (&t); + + if (r->m_oper == op_none) + { + /* .and */ + if (str_equal ((byte *) "and", op)) + r->m_oper = op_and; + /* .or */ + else + r->m_oper = op_or; + } + + mem_free ((void **) &op); + + if (get_spec (&t, &sp, maps, mapb)) + { + rule_destroy (&r); + return 1; + } + + spec_append (&r->m_specs, &sp); + } + + /* skip the semicolon */ + t++; + eat_spaces (&t); + + *text = t; + *ru = r; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int update_dependency (map_rule *mapr, byte *symbol, rule **ru) +{ + if (map_rule_find (&mapr, symbol, ru)) + return 1; + +/* (**ru).m_referenced = 1; */ + + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int update_dependencies (dict *di, map_rule *mapr, byte **syntax_symbol, + byte **string_symbol, map_byte *regbytes) +{ + rule *rulez = di->m_rulez; + + /* update dependecies for the root and lexer symbols */ + if (update_dependency (mapr, *syntax_symbol, &di->m_syntax) || + (*string_symbol != NULL && update_dependency (mapr, *string_symbol, &di->m_string))) + return 1; + + mem_free ((void **) syntax_symbol); + mem_free ((void **) string_symbol); + + /* update dependecies for the rest of the rules */ + while (rulez) + { + spec *sp = rulez->m_specs; + + /* iterate through all the specifiers */ + while (sp) + { + /* update dependency for identifier */ + if (sp->m_spec_type == st_identifier || sp->m_spec_type == st_identifier_loop) + { + if (update_dependency (mapr, sp->m_string, &sp->m_rule)) + return 1; + + mem_free ((void **) &sp->m_string); + } + + /* some errtexts reference to a rule */ + if (sp->m_errtext && sp->m_errtext->m_token_name) + { + if (update_dependency (mapr, sp->m_errtext->m_token_name, &sp->m_errtext->m_token)) + return 1; + + mem_free ((void **) &sp->m_errtext->m_token_name); + } + + /* update dependency for condition */ + if (sp->m_cond) + { + int i; + for (i = 0; i < 2; i++) + if (sp->m_cond->m_operands[i].m_type == cot_regbyte) + { + sp->m_cond->m_operands[i].m_regbyte = map_byte_locate (®bytes, + sp->m_cond->m_operands[i].m_regname); + + if (sp->m_cond->m_operands[i].m_regbyte == NULL) + return 1; + + mem_free ((void **) &sp->m_cond->m_operands[i].m_regname); + } + } + + /* update dependency for all .load instructions */ + if (sp->m_emits) + { + emit *em = sp->m_emits; + while (em != NULL) + { + if (em->m_emit_dest == ed_regbyte) + { + em->m_regbyte = map_byte_locate (®bytes, em->m_regname); + + if (em->m_regbyte == NULL) + return 1; + + mem_free ((void **) &em->m_regname); + } + + em = em->m_next; + } + } + + sp = sp->m_next; + } + + rulez = rulez->m_next; + } + +/* check for unreferenced symbols */ +/* de = di->m_defntns; + while (de) + { + if (!de->m_referenced) + { + map_def *ma = mapd; + while (ma) + { + if (ma->data == de) + { + assert (0); + break; + } + ma = ma->next; + } + } + de = de->m_next; + } +*/ + return 0; +} + +static int satisfies_condition (cond *co, regbyte_ctx *ctx) +{ + byte values[2]; + int i; + + if (co == NULL) + return 1; + + for (i = 0; i < 2; i++) + switch (co->m_operands[i].m_type) + { + case cot_byte: + values[i] = co->m_operands[i].m_byte; + break; + case cot_regbyte: + values[i] = regbyte_ctx_extract (&ctx, co->m_operands[i].m_regbyte); + break; + } + + switch (co->m_type) + { + case ct_equal: + return values[0] == values[1]; + case ct_not_equal: + return values[0] != values[1]; + } + + return 0; +} + +static void free_regbyte_ctx_stack (regbyte_ctx *top, regbyte_ctx *limit) +{ + while (top != limit) + { + regbyte_ctx *rbc = top->m_prev; + regbyte_ctx_destroy (&top); + top = rbc; + } +} + +typedef enum match_result_ +{ + mr_not_matched, /* the examined string does not match */ + mr_matched, /* the examined string matches */ + mr_error_raised, /* mr_not_matched + error has been raised */ + mr_dont_emit, /* used by identifier loops only */ + mr_internal_error /* an internal error has occured such as out of memory */ +} match_result; + +/* + This function does the main job. It parses the text and generates output data. + + XXX optimize it - the barray seems to be the bottleneck +*/ +static match_result match (dict *di, const byte *text, unsigned int *index, rule *ru, barray **ba, + int filtering_string, regbyte_ctx **rbc) +{ + unsigned int ind = *index; + match_result status = mr_not_matched; + spec *sp = ru->m_specs; + regbyte_ctx *ctx = *rbc; + + /* for every specifier in the rule */ + while (sp) + { + unsigned int i, len, save_ind = ind; + barray *array = NULL; + + if (satisfies_condition (sp->m_cond, ctx)) + { + switch (sp->m_spec_type) + { + case st_identifier: + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + status = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); + if (status == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + break; + case st_string: + len = str_length (sp->m_string); + + /* prefilter the stream */ + if (!filtering_string && di->m_string) + { + barray *ba; + unsigned int filter_index = 0; + match_result result; + regbyte_ctx *null_ctx = NULL; + + barray_create (&ba); + if (ba == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + result = match (di, text + ind, &filter_index, di->m_string, &ba, 1, &null_ctx); + + if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&ba); + return mr_internal_error; + } + + if (result != mr_matched) + { + barray_destroy (&ba); + status = mr_not_matched; + break; + } + + barray_destroy (&ba); + + if (filter_index != len || !str_equal_n (sp->m_string, text + ind, len)) + { + status = mr_not_matched; + break; + } + + status = mr_matched; + ind += len; + } + else + { + status = mr_matched; + for (i = 0; status == mr_matched && i < len; i++) + if (text[ind + i] != sp->m_string[i]) + status = mr_not_matched; + if (status == mr_matched) + ind += len; + } + break; + case st_byte: + status = text[ind] == *sp->m_byte ? mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_byte_range: + status = (text[ind] >= sp->m_byte[0] && text[ind] <= sp->m_byte[1]) ? + mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_true: + status = mr_matched; + break; + case st_false: + status = mr_not_matched; + break; + case st_debug: + status = ru->m_oper == op_and ? mr_matched : mr_not_matched; + break; + case st_identifier_loop: + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + status = mr_dont_emit; + for (;;) + { + match_result result; + + save_ind = ind; + result = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); + + if (result == mr_error_raised) + { + status = result; + break; + } + else if (result == mr_matched) + { + if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx) || + barray_append (ba, &array)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + barray_destroy (&array); + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + } + else if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + else + break; + } + break; + } + } + else + { + status = mr_not_matched; + } + + if (status == mr_error_raised) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + + return mr_error_raised; + } + + if (ru->m_oper == op_and && status != mr_matched && status != mr_dont_emit) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + + if (sp->m_errtext) + { + set_last_error (sp->m_errtext->m_text, error_get_token (sp->m_errtext, di, text, + ind), ind); + + return mr_error_raised; + } + + return mr_not_matched; + } + + if (status == mr_matched) + { + if (sp->m_emits) + if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + + if (array) + if (barray_append (ba, &array)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + } + + barray_destroy (&array); + + /* if the rule operator is a logical or, we pick up the first matching specifier */ + if (ru->m_oper == op_or && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + return mr_matched; + } + + sp = sp->m_next; + } + + /* everything went fine - all specifiers match up */ + if (ru->m_oper == op_and && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + return mr_matched; + } + + free_regbyte_ctx_stack (ctx, *rbc); + return mr_not_matched; +} + +static byte *error_get_token (error *er, dict *di, const byte *text, unsigned int ind) +{ + byte *str = NULL; + + if (er->m_token) + { + barray *ba; + unsigned int filter_index = 0; + regbyte_ctx *ctx = NULL; + + barray_create (&ba); + if (ba != NULL) + { + if (match (di, text + ind, &filter_index, er->m_token, &ba, 0, &ctx) == mr_matched && + filter_index) + { + str = mem_alloc (filter_index + 1); + if (str != NULL) + { + str_copy_n (str, text + ind, filter_index); + str[filter_index] = '\0'; + } + } + barray_destroy (&ba); + } + } + + return str; +} + +typedef struct grammar_load_state_ +{ + dict *di; + byte *syntax_symbol; + byte *string_symbol; + map_str *maps; + map_byte *mapb; + map_rule *mapr; +} grammar_load_state; + +static void grammar_load_state_create (grammar_load_state **gr) +{ + *gr = mem_alloc (sizeof (grammar_load_state)); + if (*gr) + { + (**gr).di = NULL; + (**gr).syntax_symbol = NULL; + (**gr).string_symbol = NULL; + (**gr).maps = NULL; + (**gr).mapb = NULL; + (**gr).mapr = NULL; + } +} + +static void grammar_load_state_destroy (grammar_load_state **gr) +{ + if (*gr) + { + dict_destroy (&(**gr).di); + mem_free ((void **) &(**gr).syntax_symbol); + mem_free ((void **) &(**gr).string_symbol); + map_str_destroy (&(**gr).maps); + map_byte_destroy (&(**gr).mapb); + map_rule_destroy (&(**gr).mapr); + mem_free ((void **) gr); + } +} + +/* + the API +*/ + +grammar grammar_load_from_text (const byte *text) +{ + grammar_load_state *g = NULL; + grammar id = 0; + + clear_last_error (); + + grammar_load_state_create (&g); + if (g == NULL) + return 0; + + dict_create (&g->di); + if (g->di == NULL) + { + grammar_load_state_destroy (&g); + return 0; + } + + eat_spaces (&text); + + /* skip ".syntax" keyword */ + text += 7; + eat_spaces (&text); + + /* retrieve root symbol */ + if (get_identifier (&text, &g->syntax_symbol)) + { + grammar_load_state_destroy (&g); + return 0; + } + eat_spaces (&text); + + /* skip semicolon */ + text++; + eat_spaces (&text); + + while (*text) + { + byte *symbol = NULL; + int is_dot = *text == '.'; + + if (is_dot) + text++; + + if (get_identifier (&text, &symbol)) + { + grammar_load_state_destroy (&g); + return 0; + } + eat_spaces (&text); + + /* .emtcode */ + if (is_dot && str_equal (symbol, (byte *) "emtcode")) + { + map_byte *ma = NULL; + + mem_free ((void **) &symbol); + + if (get_emtcode (&text, &ma)) + { + grammar_load_state_destroy (&g); + return 0; + } + + map_byte_append (&g->mapb, &ma); + } + /* .regbyte */ + else if (is_dot && str_equal (symbol, (byte *) "regbyte")) + { + map_byte *ma = NULL; + + mem_free ((void **) &symbol); + + if (get_regbyte (&text, &ma)) + { + grammar_load_state_destroy (&g); + return 0; + } + + map_byte_append (&g->di->m_regbytes, &ma); + } + /* .errtext */ + else if (is_dot && str_equal (symbol, (byte *) "errtext")) + { + map_str *ma = NULL; + + mem_free ((void **) &symbol); + + if (get_errtext (&text, &ma)) + { + grammar_load_state_destroy (&g); + return 0; + } + + map_str_append (&g->maps, &ma); + } + /* .string */ + else if (is_dot && str_equal (symbol, (byte *) "string")) + { + mem_free ((void **) &symbol); + + if (g->di->m_string != NULL) + { + grammar_load_state_destroy (&g); + return 0; + } + + if (get_identifier (&text, &g->string_symbol)) + { + grammar_load_state_destroy (&g); + return 0; + } + + /* skip semicolon */ + eat_spaces (&text); + text++; + eat_spaces (&text); + } + else + { + rule *ru = NULL; + map_rule *ma = NULL; + + if (get_rule (&text, &ru, g->maps, g->mapb)) + { + grammar_load_state_destroy (&g); + return 0; + } + + rule_append (&g->di->m_rulez, &ru); + + /* if a rule consist of only one specifier, give it an ".and" operator */ + if (ru->m_oper == op_none) + ru->m_oper = op_and; + + map_rule_create (&ma); + if (ma == NULL) + { + grammar_load_state_destroy (&g); + return 0; + } + + ma->key = symbol; + ma->data = ru; + map_rule_append (&g->mapr, &ma); + } + } + + if (update_dependencies (g->di, g->mapr, &g->syntax_symbol, &g->string_symbol, + g->di->m_regbytes)) + { + grammar_load_state_destroy (&g); + return 0; + } + + dict_append (&g_dicts, &g->di); + id = g->di->m_id; + g->di = NULL; + + grammar_load_state_destroy (&g); + + return id; +} + +int grammar_set_reg8 (grammar id, const byte *name, byte value) +{ + dict *di = NULL; + map_byte *reg = NULL; + + clear_last_error (); + + dict_find (&g_dicts, id, &di); + if (di == NULL) + { + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; + } + + reg = map_byte_locate (&di->m_regbytes, name); + if (reg == NULL) + { + set_last_error (INVALID_REGISTER_NAME, str_duplicate (name), -1); + return 0; + } + + reg->data = value; + return 1; +} + +int grammar_check (grammar id, const byte *text, byte **prod, unsigned int *size) +{ + dict *di = NULL; + barray *ba = NULL; + unsigned int index = 0; + regbyte_ctx *rbc = NULL; + + clear_last_error (); + + dict_find (&g_dicts, id, &di); + if (di == NULL) + { + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; + } + + barray_create (&ba); + if (ba == NULL) + return 0; + + *prod = NULL; + *size = 0; + + if (match (di, text, &index, di->m_syntax, &ba, 0, &rbc) != mr_matched) + { + barray_destroy (&ba); + free_regbyte_ctx_stack (rbc, NULL); + return 0; + } + + free_regbyte_ctx_stack (rbc, NULL); + + *prod = mem_alloc (ba->len * sizeof (byte)); + if (*prod == NULL) + { + barray_destroy (&ba); + return 0; + } + + mem_copy (*prod, ba->data, ba->len * sizeof (byte)); + *size = ba->len; + barray_destroy (&ba); + + return 1; +} + +int grammar_destroy (grammar id) +{ + dict **di = &g_dicts; + + clear_last_error (); + + while (*di != NULL) + { + if ((**di).m_id == id) + { + dict *tmp = *di; + *di = (**di).m_next; + dict_destroy (&tmp); + return 1; + } + + di = &(**di).m_next; + } + + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; +} + +void grammar_get_last_error (byte *text, unsigned int size, int *pos) +{ + unsigned int len = 0, dots_made = 0; + const byte *p = error_message; + + *text = '\0'; + +#define APPEND_CHARACTER(x) if (dots_made == 0) {\ + if (len < size - 1) {\ + text[len++] = (x); text[len] = '\0';\ + } else {\ + int i;\ + for (i = 0; i < 3; i++)\ + if (--len >= 0)\ + text[len] = '.';\ + dots_made = 1;\ + }\ + } + + if (p) + while (*p) + if (*p == '$') + { + const byte *r = error_param; + + while (*r) + { + APPEND_CHARACTER(*r) + r++; + } + + p++; + } + else + { + APPEND_CHARACTER(*p) + p++; + } + + *pos = error_position; + +#undef APPEND_CHARACTER + +} + -- cgit v1.2.3