Recreator – Simple Expressions

The recreator will work similar to the run-time module.  The run-time module will push operand values to a value stack to be popped by operators, functions and commands to perform some operation, which may push results back to the stack.  The recreator will push the strings of the operands to a string holding stack.  These strings will be popped by operators, functions and commands, which may push modified strings back to the stack or append the strings to the output string.  This will make more sense by considering this statement and its translation:

A + B
A B +

At the A operand, the string "A" will be pushed to the holding stack.  Same for the B operand with the "B" string being pushed.  The plus operator will pop the second operand, the "B" string, from the stack.  The string for the operator will be appended with surrounding spaces to the operand now on top of the stack, specifically the " + " string gets append to the "A" string leaving "A + " on top of the stack.  The previously popped second operand is then appended to the top of the stack leaving the "A + B" string on top of the stack, which may be an operand for the next operator.

For unary operators, the string for the operator is created.  A separator space is appended only for a word operator like NOT, otherwise no space is needed (for example the "-" unary operator).  The string of the single operand on top of the stack is popped and appended to the operator string.  The resulting string is pushed back to the stack.

For simple expressions, only support for operands (variables and constants) and operators are needed.  For string constants some processing is needed: all double quotes in the string of the constant need to be changed to two doubles quotes, and the entire string needs to be surrounded by a pair of double quotes.

The table entry for each code will have a pointer to a recreate function.  Since operands already have their string in the token of the item, this string just needs to be pushed to the string holding stack (with the exception of string constants).  Since this is trivial, a null pointer will indicate that the string of the token should be pushed to the string holding stack.  For string constants, there will be a constant string recreate function.  Since all binary operators work the same, there only needs to be a single binary operator recreate function.  Likewise for the unary operators.

The recreate process will loop through each item in the RPN list.  If there is no recreate function, the string of the token is pushed onto the string holding stack.  Otherwise the recreate function is called to process the token.  At the end of the RPN list, the resulting output string is returned.  For expression mode, nothing gets appended to the output list, so the tester class will need to pop the result string of the expression from the string holding stack.

Table – Simplified Instance Creation

The new recreator class will also require a reference to the single table instance like the other classes (parser, translator, and program model).  The initialization of the table reference members of these classes was not consistent - some required the table instance reference to be passed to the constructor and others accessed the static table instance directly to initialize their member.  The single table instance creation was also convoluted with several routines:

initialize - static table function to be called once (from main) to create the single instance and it made sure it was not called more than once or if the table entries had errors

has errors - static table function to return if the table has errors, used by the tester class to determine if the table entries had errors, outputs them and aborted the application

error list - static table function to return the list of error, used by the test class to output the table entry errors before aborting the application

setup and check - static table function called by initialize after creating the single table instance to setup and check the table entries

instance - static table function to return a reference to the single table instance, contains checks to make sure that initialize had been called and that the table entries had no errors; and for these errors would abort the application

The table constructor had an argument for the pointer to the table entry array and only set the table entry member.  Most of these routines were unnecessary and the single table instance creation was modified for these routines:

instance - static table function to return the single table instance, and will create the single table instance upon the first call

constructor - modified to take both the pointer to the table entry array and the count of table entries, now does the setup and check functionality, and if there are errors, they are reported and the application is aborted

Now if there are table entry errors, the constructor aborts the application and no other class needs to check for table errors.  This check was removed from the tester class.  Previously when starting in GUI mode, there was no check for table errors.  There is no longer a need to initialize the table in the main function or check to make sure it has been initialized.

The method the program model uses to initialize its table instance reference is the preferred method.  The instance function is used to initialize the table instance reference member.  The parser and translator classes were modified to use this method.

[commit 7a01ac428b]

Recreator – Testing

The recreator will take an RPN list as input.  Consideration was given to how the recreator will be tested.  There are already many tests for testing the translation of expressions and statements into RPN lists (the expression and translator test input files).  Since these are available, they will also be used for testing the recreator.

To avoid having to duplicate these into "recreator" test files, they will be used as is with a new "-to" command line option to activate the recreator on the translator output.  When this option is used instead of the "-t" option, the expression or translator input file will be translated as before, and then the RPN list will be passed to the recreator.

Since the recreator has not been implemented yet, to verify this code is working correctly, the same RPN text output is used, but prefixed with the "TEST:" string.  Encoder test input files are not supported, which will be added once the recreator is working with the expression and translator tests.

All of the test scripts and Windows batch file were updated to run all the expression and translator test files with the new "-to" test option.  Recreator output files have the ".out" extension to not conflict with the ".txt" extension used for the other test output files.  Recreator development will now commence.

[commit 9b52fc6d83]

Table – Has Operand Determination

During the development of the encoder before all of the routines were implemented, it was necessary to have a has operand flag in the table entries for codes that have an operand.  This is no longer necessary as the equivalent can now be determined by whether the code has an operand text or an encode function pointer.

The has operand flag was removed from the table entries of these codes.  A has operand table access function was added that returns whether the table entry of the code has an operand text function.  The tests for the has operand flag were replaced with this new function or use the  presence of the operand text or encode function pointer (by using the table access functions for these).

The program model operand text function is also no longer needed, which had special allowance for whether there was no operand text function for a code with the has operand flag.  The encode routine also had special allowance for this same condition, but this is also not necessary since all codes with operands have an encode function.

[commit 1e8b92e47c]

Program – Line Change Detection

The translated RPN lists for program lines is currently being saved in the line information list.  This was only temporary until the RPN lists could be encoded into program code and stored.  This mechanism was left in place since it is still being used for line change detection.  As described in the last post, RPN lists will still be compared to detect line changes except that the program code will be decoded into an RPN list.

However, the form of the decoded RPN list will be slightly different then a translated RPN list.  The method of RPN list comparison was to compare each RPN item, where the token, the attached token count, and if non-zero, each attached token was compared.  For the token comparison, the token type, the data type for constants, the code for commands and operators except the REM command and operator, the code for internal functions, the string for other token types, the reference flag, and the sub-code.

The tokens in a decoded RPN list will only have the code, sub-code (only program sub-codes), and a string (for all types).  Therefore, only these members of the token are compared.  For the RPN items, it is unnecessary to compare the attached tokens since these only refer to other tokens in the list, and the token comparisons are sufficient to catch differences, so only the attached token count needs to be compared.  In fact, a decoded RPN list will not have attached tokens, only the count, since these will not be necessary for recreation.

Token comparison boils down to comparing the code, sub-code masked by the program only sub-codes, and the string.  There is one other issue when comparing the strings that would cause the previous comparison to incorrect detect a change.  A non-case sensitive comparison must be used except for the REM, REM operator and string constant codes.

Where testing these changes in the GUI, a token (memory) leak was discovered, which occurred when the line did not change.  The program was due to the RPN list of the line to replace was not used in this case, but was not deleted.  This was corrected in additional to updating the RPN item and tokens comparison routines.

[commit 16c85dfe79]

Recreator – Design Considerations

Originally, there was going to be another module, the decoder, which would convert internal program code into an RPN (Reverse Polish Notation) token list (like the translator produces).  The recreator would then convert the RPN list back into the program text (close to the originally entered code).  Very early on (see December 19, 2009) this step was considered simple and unnecessary and so was combined into the recreator.

The program model needs to detect when a changed line has actually been changed.  The edit box sometimes reports changes lines when the line has not actually change.  The user could also have simply added spaces to the line (which are not stored) or changed the case of a keyword, which would not result in a change to the internal program code.  As previously mentioned, comparing the internal code of the current line with to the new line is problematic.

The new line would first have to be encoded, which will affect the dictionaries.  Either this would need to be undone, or the old line removed first to dereference dictionary entries only to have them referenced again when putting in the new line.  This is acceptable for simple dictionaries (variables, constants, remarks, etc.), but is much more involved with the blocking commands (IF-END IF, FOR-NEXT, etc.), where the block will probably be kept in a block dictionary.

A better alternative is to convert the program line into an intermediate RPN token list (decoded).  The translated RPN list of the new line and be compared to the decoded RPN list of the current line.  Since the decode operation can be contained in a single routine like the encode operation, the program model will own this decode routine also.

Since the decode routine will be present, then it makes sense for the recreator to take a decoded RPN list as input to convert to the program text.  This method has another advantage for testing.  Currently, the test code translates expressions and statements into RPN lists.  These RPN lists can then be passed to the recreator for testing, therefore there will be a new test mode for taking these existing tests, translate them to RPN lists, and then recreate them back to text.

Class Definition Consistency

In preparing to create the recreator class, I noticed that all the class definitions were not consistent - some had the private members at the beginning and some had them at the end.  Having the member functions at the beginning allow access functions for instance to use them, at least this was the case with early C++ compilers (or at least was my understanding when learning C++ over two decades ago).  But this does not appear to be a requirement with modern compilers.

It appears the Qt developers like to put the private member variables at the end of the class.  The public function definitions start at the beginning followed by the private section, which start with the private function definitions.  So, before embarking on creating of the recreate class definition, the non-conforming classes were changed to this style.

[commit 8fc5c92519]

Encoder/Program – Release

This concludes the integration of the encoder with the program model and dictionaries for the initial BASIC features being implemented.  The program model still keeps all of the translation RPN lists, but these are only used to detect when a line changes.  Once the recreator is implemented, these lists will no longer need to be kept.

Version 0.5.3 has been released (branch0.5 was merged to the master branch and tagged v0.5.3).  Archive files containing the source and binaries (with test files) for both Windows and Linux have been uploaded to SourceForge.  For Windows, there is also the ibcp-libs.zip file that contains all the dynamic linked libraries required to run the program if the MinGW and QtSDK packages have not been installed (extract into the ibcp directory).  Linux should already have the required libraries installed.  This concludes the 0.5 development series.

Implementation of the recreator will now begin with the 0.6 development series.  The recreator will convert the internal program code back to a reasonable facsimile of the originally entered program text.  This text will then replace the original text in the edit box.

[commit d984a70c6b]

GUI Program View – Code Output

The program view contents was changed from the text of the translated RPN list to the debug text output of the program code using the debug text routine of the program model.  The program model data function is used by the program view widget for getting its contents.  Unfortunately, this was not as simple as change as it sounds.

The data function is a constant function (const).  Because this function is constant, the debug text function also needed to be a constant function.  Making this function constant required several variables in the function to be constant, and the operand text function also needed to be changed to constant.  Changing the operand text function to constant required the table operand text function pointers to be constant.  Changing these functions required their program model pointer argument to also be change to constant.

[commit f089c78b59]

Dictionaries – Key Case Sensitivity

The BASIC language is traditionally not case sensitive.  The keyword lookup of the BASIC commands and operators are already case insensitive.  However, the dictionary lookup was not, so variables entered as VAR, Var, and var would be three different variables.  This is incorrect.  However, only one form can be stored in the dictionary.  The first instance of the variable name seen, will be the one stored.  Later there will be a facility for renaming variables.

The key map in the dictionary was changed from the QMap class to the QHash class.  These two classes are very similar for use in the dictionary class with a few differences.  The QMap class stores the key values in order and the QHash class stores them in an arbitrarily order, and QHash provides faster lookups.  Since the keys do not need to be sorted (they can always be sorted from the key list in the dictionary), the faster lookup feature is desirable.

To make the lookup of the key value case insensitive, the key string is first converted to all upper case and this all upper case string is use to lookup an index for a key and is the string stored as the hash key.  Upon the initial add of the key string to the key list, the original string entered is stored and is the string returned for all instances.

However, the remark and string constants dictionaries must be case sensitive.  Therefore a case sensitivity option argument was added to the dictionary class add routine with a default value for a case insensitive lookup.  The remark and string constant encode routines use the case sensitive option.

New encoder test #3 was added to test various forms of variables, remarks, string constants and exponential numeric constants.  Exponential numeric constants can have either an upper or lower case 'E' for the exponent.  Again, the first instance of the constant seen will be stored, so the user can decide which form is desirable.

[commit da56095d1a]

Program – Enhanced Line Debug Output

The program view will get the same output as produced at the end of encoder test output, which includes the offset range, and the debug text or the error information (column, length and message) of the line.  Currently a program line with an error does not have any code associated with it (an input error).  However, for a code error, the program line will have been successfully encoded and stored into the program.  An example of a code error is a missing ENDIF to an IF.

The generation of the line offset range and error output was moved from the tester class to the program model debug text routine so that it can also be used for the program view.  This code was also modified to output both the debug text and the error information instead one or the other.  Since input errors have no code, this works as before.

Since the debug text routine is also used by the tester class encode input routine to just obtain the debug text for a line, the debug text routine was given an flag argument for whether to return the full information (offset range, debug text and error information) or just the debug text.

The error information is handled differently by the encode input routine, where the error column and length are used to point to the error.  This was modified to get a pointer to the error item for the line instead of the RPN list using the new error item access function added to the program model class, which returns a null pointer if the line does not have an error.

[commit 3fde3da2e0]

Program – Delay Line Encoding

The edit box class has an issue where sometimes unmodified lines are reported as being changed.  There is currently a check when replacing a program line where if the line has not changed, no action is taken.  Currently the translated RPN list is compared to the stored RPN list for the line.  Eventually however, the RPN lists will not be stored and this line change detection will have to be changed.  More on this later, but this change will be made once the recreator is implemented.

A newly translated line can't be encoded until it has been determined that the line has changed because the process of encoding adds or updates references in the dictionaries.  If the line then hasn't changed, this would need to be undone, which would be unnecessarily complicated.  Therefore, the encoding of the line was delayed until after it is determined that the line changed.  Since this does not affect new line insertions, the line also needs to be encoded for the insert operation.  The line is only encoded in both places if there was no translation error.

[commit b5c9020cc8]

Program – Removing RPN List Dependency

The pointer to the RPN list of a program line from the translator is currently being held in the line information list for the program (along with offset and size of the line and an index to the error list if the line has an error).  This pointer will eventually be removed since the RPN list is not needed after a line is encoded and stored in the program.  There were two dependencies on the RPN list that needed to be removed.

The program model update error routine used the RPN list from an line information list item to determine if the line has an error.  If it did, an error item is created from the RPN list (retrieving the error column, error and message) and stored in the error list.  The index of the error item in this list is then stored in the line information item for the line.

Since the RPN list pointer is going to be removed from the line information list, the update error routine was modified to obtain the error information differently.  Instead of creating the error item in this routine, the error item is now created in the calling update line routine just after the line is translated and checked for an error.  The error item with the error information is passed to the update error routine, which was modified to use it instead of the RPN list.

So that an empty error item can be indicated, a new none error type was added to the error item class.  An is empty access function was added to return if the error item does not contain an error.  A default constructor was added to create an empty error item.  Also for clarity, the translator and encoder error types were renamed to the input and code error types.

Even though currently no encoder errors can occur, the error item constructor was modified from having an RPN list pointer argument to having arguments for the error column, length and message.  This will allow setting errors from encoding without an RPN list (the error item class is no longer dependent on the RPN list class).

[commit 0a10ddae84]

Program – Dictionary Debug Output

The program debug output shows the indexes of dictionary entries, but this is insufficient for showing if the dictionary entries were removed correctly and are placed on the free stack of the dictionary for reused.  Code was added to output the contents of each dictionary.

The debug text routine was added to the dictionary class that takes a header string as an argument.  After appending the header string to the output string, it loops through the dictionary entries and appends the index, use count and string of every entry with a non-zero use count.  After the entries, the indexes in the free stack are appended.  If any free stack item contains a non-zero use count, the use count is appended after the index.  Also, if the item has a non-empty string, the string is also append.  The strings of deleted entries should be cleared.

The debug text dictionaries routine was added to the program model class, which calls the debug text routine of each dictionary and appends each to the output string.  A call to this routine was added to the tester class run routine after the program model debug text function is called to output the program code.  The expected results for encoder test #1 and #2 were updated for the additional dictionary debug output.

[commit 11337cb673]

Program – Dereference Removed Lines

When a line of code is replaced or removed, the use counts of any dictionary entries referenced on the line need to be decremented.  If the use counts becomes zero, the entry is no longer being used and needs to be deleted from the dictionary (the entry becomes available for use by another item upon the next add).

The dereference routine was added to the program model to scan a line that is about to be replaced or removed.  This routine loops through each program word of the line and removes the reference for any code that has an operand, which is determined by whether the code has a remove function.  In the update line routine, this routine is called before the line is replaced or removed.

Table entry remove functions were added for the various REM, constant and variable codes.  Each remove function calls the remove routine of appropriate dictionary (just like the encode function calls the add routine of appropriate dictionary to add a reference).

Encoder test #2 contains replace and remove operations, but previously the use counts of dictionary entries were not being decremented.  Now that they are, several dictionary entries are now removed since their uses counts become zero and are removed from the dictionary.  This allowed new items to be added in the unused entries, which affected the index of several dictionary entries on some of the program lines, therefore the expected results were updated.

[commit a310dc458e]

Program – Error Handling Issues

When checking for memory errors, a use of uninitialized memory error was detected with new encoder test #2.  The problem occurred in the remove error routine, which was always adjusting the rest of the errors after the current line.  It should have only been doing this if the line was not deleted and did not have an error.  Because this routine did not return for this condition, the error index loop variable was not initialized causing the memory error.

When the update error routine was modified back to not returning the status of whether the line has an error, the routine was not changed back to its original code correctly.  This caused errors not to be added to the errors list and therefore did not show up when running the GUI.  The routine was put back to its original code from an earlier commit.

When a line was replaced with an empty line (for example, a line with an error), the replace line routine of the new LineInfoList class was supposed to call the remove line routine and then return.  Instead if was calling the base QList class remove routine and not returning.  This caused extra code to be removed from the program.

A line with an error was added as a replacement line to encoder test #2 to verify the corrections described above.  The offset for a line with an error was added to the test output to verify that errors lines are added to the program correctly.  The offset is needed for when the line with the error is replaced with good code.

[commit d8ef155e5e]