Table Alternate Codes – Operators/Functions (Use)

With the new alternate codes map implemented and partially filled with all the alternate codes for operators and internal functions, the translator was modified to start using this map instead of the associated codes array.

Two access functions were added to the table class, which included the alternate code and alternate code count functions.  Both take code enumerator and operand index arguments.  These functions have temporary implementations.  When the new table model is fully implemented, these functions won't need the code argument as the this pointer will be used as the key to the map.  They will also return a entry pointer instead of a code enumerator.

The binary operator check for a unary operator in the translator get expression routine was modified to use the new access functions.  In the process internal function routine, the new access function is used to get the alternate code for a function for an operand of a different data type as the primary function code, and when an extra argument is found for a function with multiple forms.

There was an issue with the subtract code table entries.  The current associated code arrays are still being used to process operands of operators because the find code routine is still being used to get associated codes for codes that don't have entries in the new alternate map yet, so couldn't be modified to use the new access functions.

The problem was caused by the change to make the main binary subtract code (two double operands) the second associated code of the negate code, which was made the primary code for minus operator.  This subtract code was moved to after the subtract code with the first integer operand.  Since this code was first, it was made the main binary code and the primary binary alternate to the negate code.  This code did not have the correct associated codes on the current associated code array, so hidden conversion operators were incorrectly added to the output list.

This order of the alternates in the table does not matter with the alternate generation, but for the moment, the new alternate map and the associated code arrays need to agree.  This problem was corrected by moving the main subtract code to before the subtract with first integer operand.  Since the code enumeration is not automatic, the subtract enumerator also had to be moved to match the table.  This is a temporary situation.

[branch table commit 01db8002ba]

Table Alternate Codes – Operators/Functions

The alternate codes map will be implemented in a number of steps including adding alternate codes automatically for operators and internal functions, using the alternate map for operators and functions, removing the associated codes for operators and functions, manually adding alternate codes for internal codes, using the alternate map for internal codes, and adding additional alternate codes (to further reduce the need for code enumerators).

First, the definition for the alternate code static map member was added to the table class along with its instantiation in the table source file.  The standard array is new to the C++11 STL and is just as efficient as a built-in array with improvements.  Since the definition is quite lengthy, it was broken into two definitions (there was no reason to define a constant for the 3 since this is the only place that it is needed; indicating up to three operands or arguments):

using EntryVectorArray = std::array<std::vector<TableEntry *>, 3>;
static std::unordered_map<TableEntry *, EntryVectorArray> s_alternate;

The add function was modified to add an entry as an alternate code if appropriate.  Alternate codes are based on having the same name as another code.  If an entry name is newly added to the name to entry static map, then the routine returns immediately, in other words, the code is a primary code.  If the name is already in this map, has an expression information structure, has operands, and does not have its Reference flag set, then the entry can be added as an alternate code.

If the operand count of the entry is less than the count of the primary code, then it should be the primary code.  In this case, the pointer to the entry replaces the value in the name to entry map, and the previous primary is made an alternate code of the entry, by adding to the array element for its operand count minus one, and returning.  This was a better solution then reporting an error.

The routine does a series of comparisons between the operand data types of the entry with that of the primary to identify which primary code it should be added as an alternate to.  If all the operand data types of the primary code match that of entry and the entry is an internal function with more operands, then it is made an alternate of the primary in the array element one less than the operand count.  This is a multiple argument entry (ASC, INSTR or MID$) so the Multiple flag is set on the primary code.  Otherwise, the entry has duplicate operands as the primary and an error is thrown.

Since the Multiple flag is set automatically, it no longer needs to be specified in the table entry array initialization.  Also since this is automatic, and the requirement that a multiple entry be in the following entry in the table was eliminated, the validation of multiple non-assignment entries was removed from the table constructor.

Using the debugger within QtCreator, the alternate map was verified to be setup correctly.  At this point however, this new alternate map is not being used.  This will be the subject of the next change, which will be to use the alternate map for the operators and internal functions instead of the associated code arrays.

[branch table commit b7021a78ae]

Table – Alternate Codes Map

The handling of alternate codes (formally known as associated codes) will be handled differently in the new table model.  In the current table model, each code in its expression information structure contained a single array of associated codes along with a count and an index to a second set of associated codes within the array.  In the new table model, these will be removed from the expression information structure.

The new table model will contain the information for a code in a single table entry instance, which will be handled by a pointer.  The table class will contain some static data members (members shared by all instances).  The alternate code information will be stored in one of these new static data members, specifically a map from a primary code table entry pointer (the key) to its alternate codes (the value).

The value of this alternate map will contain an array (a standard array will be used) of three elements.  Each element represents the alternate codes for a particular operand.  Generally, the first element (index of 0) will have alternate codes where the data type of the first operand is different from the primary code.  The second element will have alternate codes where the data type of the second operand is different from the primary code.  This was roughly the purpose of the second associated codes.

The third element of the array is applicable only for three argument internal functions, which is new.  There are currently no planned internal functions that have different data types in the third argument.  This third element will be used to associate three argument functions to there primary code with two arguments.  This applies to the MID$ and INSTR functions which have two and three argument versions.  This similarly applies to the ASC function, but its second form has two arguments, so the second element of the array is used.

Each element of this array will contain a vector of alternate code table entry pointers.  A particular element may have an empty vector indicating no alternate codes with different data types for that operand or argument.  The first step will be to automatically generate this map from operator and internal function table entries from the operand data type information.

Table – Code Enumeration Increment Functions

Before the code enumeration can be changed to a C++11 enumeration class, the increment operators need to be removed (though they could be made to work with an enumeration class by using static casts, but this not desirable).  There were only two uses of this increment operator.

One use of the code increment operator was in the assign string recreate function for sub-string assignments, where the name of the function was used to find the original sub-string function code.  If the sub-string function has multiple entries (MID$), then the sub-string code is incremented.  For functions with variable number of arguments (ASC, INSTR, and MID$), the second code with an additional argument followed the first code, which was required for the increment method to work.  The sub-string code was used to recreate the sub-string assignment.  The sub-string code was needed since it had the correct number of operands (the sub-string assignments did not).

The assignment, list assignment and string keep assignment code entries were given one operand for the data type of the value being assigned.  Only this first operand data type was used and it did not matter if there were more operands (the count of operands was not used), so the sub-string assignments were given the same operand data types as the sub-string functions (the sub-string keep assignments already had these operands).  With the correct operands, the sub-string assignments assignments can be recreated directly without having to look up the sub-string function code, eliminating the need for the code increment operator.

The set token code function is used to set the correct code for the operand data type.  One use is for operators to set the correct code for the data type of its operand.  The second associated codes  are used for the second operand.  A negative second associated code index indicates no second associated codes.  A negative index was only used by the sub-string functions to prevent it from using any of its associated codes).  The set token code function is no longer called for functions, so this check was unnecessary.  The negative index was removed from the sub-string code entries.

The other use of the code increment operator was in the translator process internal function to move to the next code a function with variable number of operands (ASC, INSTR, and MID$mentioned above).  The token next code access function was used to increment the code.  The second code of these functions were associated to the first code, so now when a comma is processed for the next argument instead of a closing parentheses, the second code is obtained by getting the associated code of the first code.  The next code function was removed along with the code increment operator functions.

[branch table commit e5b55fa271]

Table – Code Enumeration

With the new table model, the code enumeration will be a subset of the current code enumeration and will only include codes that are referenced (for example, Comma, Equal, Semicolon, Open Parentheses, Closing Parentheses, etc.).  With the bracketing codes removed, all the remaining code enumerators represent actual codes.  The current auto-generated code enumeration was copied to the main header file.

Temporarily, the code enumeration definition must match the table entry array and there are no checks to insure this (which was the purpose of auto-generating the code enumeration).  Since the code enumerators are still used as indexes, this enumeration was not changed to a C++11 enumeration class yet.  There are also some in-line functions for incrementing a code enumerator, which is possible since plain enumerators can be used as indexes, but more difficult with an enumeration class.  Notes were added to which enumerators will be removed.

The enumerations awk script was removed.  The CMake build file was modified to remove the auto-generation of the code enumeration header file.  Since the awk program is no longer used, looking for this program was also removed.  The next goal will be remove the use of code enumerators as indexes so that this enumeration can be changed an enumeration class.

[branch table commit 9a3c075ba0]

Table – Name Lookup Mechanism

In order to eliminate the auto-generated code enumeration, unnecessary code enumerators will be removed.  Table bracketing entries were used to break the table into search groups.  There were three of these groups, which included plain words (including two-word commands), words with parentheses, and symbols.

When the table was initialized, the start and end of each group was determined and stored in the range member indexed by the search type enumerator.  This enumeration was not changed to a C++11 enumeration class because its enumerators were used as indexes.  When a caller wanted to search the table for a name, it passed one of these search types and the search looked only within that range (by sequentially iterating over the entries).

The new name lookup mechanism uses a standard unordered map where the key will be the name of the code and value will be a pointer to a table entry.  For two-word codes, the two words are combined with a space separator between words.  The key hash and key equal function operators defined in the dictionary class were moved to the utility header file and renamed to case optional.  These are used for this map, defined as a static member, so that searches are case insensitive.

The search functions were renamed find to mirror the standard library names and were made static.  The primary find function calls the map find function with the string argument.  If the string was found then the code index is calculated by subtracting the base table entry pointer from the table entry pointer, otherwise the Invalid code is returned.  After the new table is fully implemented, the table entry pointer itself will be returned or the default table entry pointer.  The find function for two words combines the words with a space separator and calls the primary find function.

The add function was added to add an entry to the table, which now just consists of adding to the name to entry pointer map.  This function is called at the beginning of the entry iteration loop in the table constructor and throws an exception (a string) if an error is found (a two-word code is already in the map).  Eventually this code will be put into or called from the base table constructor.

The search type enumeration was removed along with the bracketing table entries (include their code enumerators) and the range member used to hold the indexes of the bracketing entries.  The End Plain Word bracketing code was used by the unary operator recreate function to determine if a space should be added after the operator it is a name and not a symbol.  This check was changed to checking if the last character of the operator name is a letter.  There was also a match function that was no longer used and was removed.

[branch table commit f5f563cad2]

Table – Initialization (Errors)

Before creating the name and alternate code maps, the table constructor was modified to use a standard vector of standard strings to record table errors.  Any errors found are then output to the standard error stream.  Finally, the standard abort function is called to terminate the program when errors are found.  The translation call was also removed as this isn't necessary because these errors are programming bugs not requiring translation.

[branch table commit 70f9125512]

Table – Name and Alternate Code Maps

Since the table source file is going to be receiving a lot of changes, the immediate goal is eliminate the auto-generated code enumeration header file so that the entire project doesn't need to be recompiled for each change to the table source file.  This will be accomplished by changing how code enumerators (indexes) are handled.

A code enumeration will still be required for a limited number of codes that are referenced throughout, for example, the special operators like Comma, Equal, Semicolon, End-of-Line, etc.  So there will still be a code enumeration, but it will not be used as an index to codes.  Currently however, there are many more code enumerators that are used, specifically the range code enumerators and the code enumerators used for the associated code arrays.

The range code enumerators will be removed first.  To accomplish this, the search mechanism will be changed, which currently searches for a name within three different ranges (plain words, parentheses words, and symbols) of the table entry array.  The new mechanism will have one-word names in a name to table entry pointer map.  The two-word names will be in a separate two-word names map.  These maps will be static table members.  The table entry structure members will eventually be in the new table class, so these table entry pointers will become table instance pointers.

When the table consists of many code table instances, the base table class constructor will setup these maps when the constructor of the code classes calls it.  For now, these maps will be setup in the current single instance table constructor when it iterates the table entry array.

Similarly, there will be maps from code table instance pointers to vectors of table instance pointers for alternate codes (the new name for associated codes).  These static member maps will also be setup by the new base table class constructor, but will temporarily by setup in the current table constructor.

Table – New Model

One of the major goals for the new table design (missed in the December 3 post) is to eliminate all the standalone code work functions (translate, encode, recreate, etc.), which require their definitions so that pointers to them can be put into the table entries.  Many of the codes do not have several of these work functions (for example, only commands have translate functions), and many codes share work functions (for example, all binary operator have the same recreate function).  Once all the codes are implemented, there would have been an explosion of these work functions, especially considering that each code will need a unique run function.

Therefore, a class hierarchy will be the basis for the new table model where the base class holds the information members and virtual functions used for these functions.  Using virtual functions allow defining common work functions in an upper class.  Unfortunately, there will be an explosion of classes since all codes need a unique run virtual function.  Fortunately, there is a way to define these classes without requiring every source file to know about them so only the base table class needs to be known globally, which will contain the interface for all of these derived classes.

There will be a table instance for each code containing the information for that code only.  Instead of identifying a code by an enumerator (essentially an index), a code will be identified by a base table class pointer.  Code information will be accessed by inline access functions, and the work functions accessed using virtual functions.  The index of the code will only be accessed when a token is finally encoded into the program.  Each code will be assigned a unique index during initialization (more on this later).  The token will therefore contain a code table instance pointer instead of a code enumerator (index).

Though there will no longer be a monolithic table instance, there will be some static table class members and functions.  For example, the search functions will be static since these will not require a table instance (they will return an instance for a code).  The search functions will use a static map member for looking up a name to get a code table instance.   Each of these static members will be described as they are created.

Table – Current Model

The model of the current table design is a monolithic single instance where the information for each code is obtained with a code enumerator that is used within the table as an index into an array of plain structures where each element contains the information for a single code.  There is a series of access functions taking a code enumerator as an argument.  There is a similar series of access functions taking a token as an argument, where the code enumerator stored in the token is used.  Finally there are a couple of functions for searching the table for a code by a name.

A singleton pattern was used for the table instance so that a global table instance would not be used.  However, the table entry array was global (though only within the table source file) along with a static pointer to the instance (within the table class and defined in the table source file).  Is this really a singleton?  In any case, this singleton pattern will be temporarily replaced with a single global table instance (until the new table model starts to get implemented).

One problem with the current table is when it comes time to add a new variable to a table entry structure, like the just added expected data type member.  If a value for one of the entries is missed, the compiler reports the error, but error is reported against the end of the array giving no clue which entry has the problem.  Finding the problem entry is very time consuming.  (This actually occurred).

Another problem is with the auto-generation of the code enumeration.  The actual code enumerators were defined as comments in the table source file, which a awk script combed through an generated a header file with the code enumeration definition.  This design was an attempt to eliminate the problem of matching the code enumeration with the entries.

This issue was that this auto-generated header file is dependent on the table source file, the main header file includes this header file, and all source files are dependent on the main header file.  So every time the table source file is modified, the entire project needs to be rebuilt, and this is becoming a nuisance.  Therefore, the first goal will be to eliminate this.

Pre-Table – Expected Data Type

The expected data type member of the Expression Info structure was initialized during table initialization based on the type (operator or function), number of operands and data types of the operands.  This variable was moved to the table entry so that the preset expression info instances are not modified.  This resolved the issue with the REPEAT$ function.  An initialization value needed to be added to all of the table entries, a drawback of the current flat table entry array (though this will be changed in time).  The default data type value was used.

This is about the end of the preliminary changes for the table.  The next post will begin to describe the new table design.  Since the changes will be significant, an attempt will be made to transition to the new design in a series of smaller changes.  The movement of the expected data type could be considered the first of these changes.

[branch table commit 81992b2d51]

Pre-Table – Expression Return Data Type

The data type table entry member was originally used for both the next expected token data type for a command and the return data type for operators and functions.  The next expected data type was used with the now replaced token centric translator.  Since the translator is now command centric, a next expected data type for commands is not needed.  Since the return data type is expression related, it was moved into the Expression Info structure.

The preset expression info structure instances were updated to include a return data type.  The table entries were updated where the data type initialization value was removed and the expression info structure pointer name updated or the return data type value added to the expression structure constructor call.

For the REPEAT$ function entry, the same preset expression info structure instance that is also used by several assign operators could not be used since the REPEAT$ function required a different expected data type.

The data type access function was replaced with a return data type function that checks if the expression info structure is present before attempting to access the return data type member.  If the structure is not present, the None data type is returned.

[branch table commit 0186dcb76b]

Pre-Table – Multiple Member

The multiple table entry member identified codes that either could be the first word of a two-word command (for example INPUT), was a two-word command (INPUT PROMPT), could be the first character of a two-character operator (<), or was a two-character operator (<=).  Having an entire member for just this was unnecessary since a flag could be used for this purpose.  In addition, it was not necessary to identify two-character operators.

Therefore, the multiple table entry member was replaced with a new Two table flag (a Multiple table flag already existed) and its access function removed.  The Multiple enumeration contained separate enumerators for both characters and words, though were assigned to the same value and even contained enumerators for three characters or words, even though there were no codes that used these.  This enumeration was removed.

Some changes were made to the Table Flag enumeration, including assigning it an underlying type of an unsigned integer (32 bits).  Instead of assigning the enumerators to hard to read hexadecimal constants, they were assigned values using the shift operator where an unsigned one value is shifted by a unique number of bits.  The shift operation is calculated during compilation.  The Null table flag enumerator was removed; the default table flag value (TableFlag{}) is used instead.  The flag table entry member type was also changed to an unsigned integer.  The has flag access functions were changed to return a boolean value.

The parser get identifier and get operator routines were updated to use the has flag access function with the Two flag instead of using the multiple access function.  In the table header file, there were a few remaining previously missed uses of a Qt type (quint16) on function pointer definitions that were replaced with the standard equivalent type (uint16_t).

[branch table commit 2f5edfc30e]

Pre-Table – Unary Operator Detection

The expression information structure within the table entry contained a unary code member, which was used to determine if a code was or could be a unary operator.  This member contained the code of the unary operator or a null code.  Only four codes contained a non-null code, which included the two negate codes (double and integer), the NOT operator, and the main subtract code.  The subtract code contained the first negate code, but the others contained their own code.

This was not efficient use of the member as it was only used for four codes especially considering there was another way to determine a unary operator, namely checking if token type is Operator and the number of operands is one.

This required a change in how the negate and subtract operators are associated with each other.  Originally these codes were not associated as the unary code member was used to get from the subtract code to the negate code.  Without the unary code member, an association was needed.  It did not make sense and was problematic to associate the negate code to the subtract code, which already had a number of associated codes.

Therefore the subtract code was associated with the negate code as a secondary associated code (the negate code already has the integer negate code associated to it).  Making it the second associated code makes sense as the subtract has two operands.  This change required some changes with how the translator handles unary operators.

When getting an operand, the translator get expression routine checked if the current token was a unary operator, and if it was, changed it to a unary operator.  Now it just checks if the current token is not a unary operator before calling the get operand routine.  When getting an operator, if the operator was a unary operator, an error was thrown immediately.  This was changed to check if the unary operator has a secondary associated code (a binary operator), it if it does, the token is changed to the secondary associated code, otherwise an error is thrown as before.

The table initialization that sets the expected data type member was changed to look through the primary associated codes only for unary operator instead of the secondary associated codes.  There was an is unary operator function definition in the table class definition that was not used and didn't have a function, so it was removed.  The unary code argument was removed from all of the expression info constructor calls.

[branch table commit b472f6a36d]

Pre-Table – Sub-String Assignments

In researching the requirements for the new table design, specifically how to implement associated codes (which will be renamed alternate codes), there was an issue with the associated codes for sub-string assignments (LEFT$, MID$ and RIGHT$).

The sub-string assignment codes are the first associated code for the sub-string codes.  The sub-string assignment-keep codes are the first associated code of the sub-string assignment codes.  For recreation, the original sub-string code was the second associated code for each of these assignment codes.  This was necessary since the sub-string code contained the actual number of arguments as the sub-string assignment codes contain only two arguments (one for the value and one for the reference being assigned).

This circular association back to the original sub-string code was going to be a problem with the new table design and so the sub-string code associated were removed.  The first change made to the sub-string assignment table entries was to put back the original sub-string keyword name.  Since the debug name is the combination of the primary and secondary names, the secondary names were changed to remove redundancy, for example, the debug name for AssignLeft changes to LEFT$(Assign.  The affected expected test outputs were updated accordingly.

The assign string recreate function was modified to use the keyword name to look up the original sub-string code instead of using the second associated code for the sub-string assignment codes.  This caused a problem with the MID3 codes as the MID2 code was found, which contained the wrong number of arguments.  This was resolved by adding the Multiple table flag to the MID3 codes.  When this flag is set, the sub-string code found is incremented to the next code.  This change caused a problem during table initialization checking, which was modified to only check Multiple flagged entries if the Reference flag is not also set.

The assign string recreate function was also using the fact that the second associated index was set zero to detect an assignment-keep code (which are used in string list assignment statements).  The string built so far needs to be put back onto the recreation stack.  With the above changes, the assignment-keep codes no longer have associated codes.  This was resolved by adding a new Keep table flag to identify the assignment-keep codes.

[branch table commit f0c7ebdacd]

Pre-Table – Maximum Checks

There were two constants defined in the table source file, one for the maximum number of operands and one for the maximum number of associated codes.  During table initialization, while it is iterating over all of the table entries, it looks for the largest operand count and associated code count for any entry.  If these largest values are larger than the maximum, then a table initialization error occurs (the application then aborts).

I was not able to determine why these constants and checks were put in.  There is nothing that necessarily limits the number of operands or associated codes.  These maximum constants were only used for these checks.  Therefore, these constants and checks were removed.

[branch table commit 489c59904c]