Translator – Array Assignments

There's been a change of plan for the Translator handling arrays on the left side of assignment statements, which will be explained in the next post. What was needed to handle array subscripts was a stripped down routine similar to the code routine, to handle integers and doubles (for which a hidden CvtInt code would be added). As the customized new function was being implemented, some unnecessary code was found.

In the find code routine, when the token with an error was not a reference, there was a check if the last token added to the output was different from the token on the done stack, and if it was, it was assumed that the last token was a sub-string function (which was not put on the done stack because its operand was left on the done stack). So this sub-string token was returned for the error instead of the token on top of the done stack.

In addition, if the last token was not the expected sub-string function, a bug error was returned since it was assumed to be invalid condition. However, this is a valid condition if a dummy close parentheses token was added to the output, which would then be the last token added to the output.

With the first and last operand implementation, these checks are no longer necessary, since the for sub-string functions, the first operand left on the done stack acquires the sub-string function token as its first operand and this first operand token is returned as the location of the error.  Therefore, these extra checks were removed.

Translator – Correcting More Token Leaks

There were a few more token leaks that needed to corrected, one with the first and last operand changes and rest with the PRINT command. Details of the rest of the token leaks found and corrected are after the continue. All tokens leaks have now been corrected, time to handle array assignments...

Translator – Correcting Token Leaks

The crash on Translator test 12 was caused because the token leaks were only being output after a successful translation but not when an error was reported. After a number of errors, the token leaks built up and when they were finally output, their information didn't line up with the current input line causing a crash when accessing outside of a buffer. Once that problem was fixed, the token memory leaks were fixed one by one.

For one of the leaks, an incorrect fix was applied causing multiple token deletes. For some reason these tokens were not output. A segmentation fault occurred when attempting to debug this problem before it even got to the output code when it was attempting to delete the string in the token a second time. Setting the string pointer to NULL didn't help – apparently the memory was already being used for something else.

Apparently gdb (under NetBeans) catches these segmentation faults where the program running by itself does not. In any case, at least the code was at least detecting the extra delete condition.  Details of the memory leaks found and corrected so far after the continue. A common theme is that the token leaks occur when something is popped from the stack and not put anywhere because any tokens in any of the stacks, the pending parentheses token or the output list get deleted by the Translator's cleanup routine.

Token Leaks – Implementation

To implement token leak detection, a token pointer list was added to the Token class as a static member and a token list element pointer was added as a regular member.  The new and delete operators were overloaded in the Token class to be able to maintain this token list.

The overloaded new operator function first allocates an array of bytes for the size argument, which is type cast to a Token pointer. The token pointer is appended to the static token pointer list and the element pointer returned from the list append function is put into the element pointer member of the token. The value of the token pointer is returned.

The overloaded delete operator function type casts the void pointer to a token pointer. If the element pointer is NULL, then this token has already been deleted. Otherwise the element pointer in the token is used to remove the token pointer from the token pointer list. The element pointer of the token is set to NULL to indicate that it has been deleted (to detect multiple deletes of the same token). The memory used by the token is then deleted.

This additional error that can occur when a token being deleted more than once. To also catch these errors, when a token is being deleted, if its element pointer is NULL, then a copy of the token will be added to a new delete list, which will be a list of tokens. A copy of the token needs to be made because the memory has already been deleted and could be reused by another allocation. It's also possible that the memory may have already been reused and the token copy will be garbage, but at least it will be known there is an extra delete somewhere.

Finally, the test code was modified to output any tokens that have not been deleted once the RPN output list has been output and cleaned up (all of its tokens deleted). The tokens in the delete list are also output. Once the code was working and running, many token leaks were found (in six of the Translator tests), and Translator test 12 (more error tests) was crashing. Time to fix some problems...

List Class Update

The List class is currently keeping track of the beginning and end of the linked list with a master element. The master element is created when the list is created. A list element contains a previous element and next element link pointers along with the value of the element. The amount of memory allocated for the master element is less the element value using a strange syntax for subtracting the size of the value from the total size of the element – not ideal.

When a list is created, the links of the master element are set to point to the master element itself.  The list is empty when the master element's next and previous pointers are the same as the master element pointer. When linking through the list, the first element is the master element's next pointer. The end of the list is detected when the master element is reached when linking to an element's next pointer.

In considering a design for the token linked list, it was realized that the master element is not really necessary. All that is needed is a pointer to the first element in the list. Or, for a first-in-last-out list, a pointer to the last element. The last pointer method will be used and the variable will be named tail. The list is linked circularly meaning that the last element's next pointer points to the first element in the list and the first element's previous pointer points to the last element. If the list is empty, then tail will be set to NULL.

Using the single tail pointer, the first element in the list is now obtained using tail->next assuming the list is not empty, otherwise NULL will be returned. The last element is now obtained simply by using tail. When appending items to end of the list, the new element is linked into the list and tail is set to the new element. When removing the last element from the list, a check is needed to see if the list is empty after removing the item.

Sourceforge Uploads Now Working

Sourceforge is accepting uploads again and the files for the latest pre-release are now there.

Token Leaks – Initial Design Thoughts

When considering a design to keep track of tokens created, there needed to be an easy way to remove the token once it has been deleted. Tokens left in the list would be memory leaks. The first idea was a simple linked list where each element consisted of a previous link, a next link, a pointer to the token and some type of identifier of where in the code that the Token was allocated. A pointer to the list element would be added to the Token class.

When a token is created, it would be added to the list and a pointer to the list element would be put into the token.  When a token is deleted, it would use the element pointer to delete the item from the list. For tokens still in the list at the end, the identifier would indicate where the token was created, though the contents of the token itself would probably be sufficient in determining why it was not deleted.

At first, a special token list class was considered. It would only need a pointer to the first element in the list. Some code on how this would work (adding and deleted elements) was sketched out.  But wait, there was already a List class, and then it was realized that the List class doesn't need a master element to keep track of the first and last elements in the list. Only a pointer to the first (or last) element is needed...

Memory Leak Detection

Memory leaks have been a continual problem. Frequently another one is discovered like the recent pending parentheses issue. Some short of memory leak detection is needed. In C++, the new and delete operators can be overloaded so that a custom memory management can be used. While this is a possible solution, a memory manager with leak detection can be very involved. Something simpler is desired.

Analyzing the current source code, looking for all the uses of new operators currently used, here's what was found:

Tokens – allocated in a number of places; these have been where most of the memory leaks have been found

Strings – for now these are allocated when creating tokens, so if the tokens get deleted these will get deleted (in the Token destructor)

Stacks – the arrays in the stacks upon first creation and when expanded; the arrays will be deleted when the stacks go out of scope (as part of the destructors of the classes that use them)

Lists – the elements of the list, which are deleted when the lists go out of scope (as part of the destructors of the classes that use them)

Translator Output list – this is a one time allocation in the Translator when a new translation is initiated; it is handed over to the caller when getting the translated results; so it's up to the caller to clean this up (currently handled in the test code)

RpnItems – everyone of these that are allocated is appended to the Translator's output list, so these will be handled when this list is cleaned up

Table – one time allocation in the main function, which is not important as there is only one, but a delete was added at the end of the main function

Error Lists – these are allocated as part of the Token and Table initialization when an error is detected, but were never deleted, which is not important as these were only created when there was an error (and the program exits), but deletes were added

So it looks like Tokens are the only specific area where there is currently a problem with  memory leaks. Next, a simple solution for detecting token leaks...

Sourceforge Not Accepting New Uploads

Sourceforge does not appear to be accepting new uploads at the moment.  Last night it just seemed to be taking a long time to be distributed to the mirrors, but this morning the same message appeared.  This may explain the problem.  For some reason it did except the new release notes.  For now the previously posted link for the latest pre-release does not work.

Translator – First/Last Operand – Pre-Release

The first and last operand changes are now working and all tests are working correctly except for three statements in Translator test 12 (more error tests). The expected results for these statements were changed in anticipation of having the Translator assume that tokens with parentheses on the left side of an assignment are arrays since functions with arguments will never be there. However, one little issue remains. Consider these statements:

Z$ = A$ + (B + C)
Z = A + (B$ + C$)

Because the open and close parentheses are now attached to operator tokens, the second + in the two statements above, when the error is detected (at this +), the whole parenthetical expression including the parentheses are reported instead of the expression within the parentheses. This new behavior is reasonable so it will be left as is for now.

This is a good time to make another pre-release before continuing. The file ibcp_0.1.14-pre-4-src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program. Now, before continuing on, it's time to do something about detecting memory leaks...

Translator – First/Last Operand – More on Parentheses

An old undiscovered bug was found where the pending parentheses token was not deleted when the previous token added to the output list's parentheses sub-code was set when it was determined that the parentheses was not necessary (the parentheses sub-code allows the parentheses to be reproduced). This again emphasizes the need for memory leak detection (more on this soon).

There was a conflict between a closing parentheses token being used as a pending parentheses and as a last operand. It's possible that a pending parentheses will become a token added to the output list (occurs when there are two sets of unnecessary parentheses), so when this token is no longer needed as a last operand, it can't be deleted. The solution was for two new sub-codes, one where the closing parentheses token is being used for a pending parentheses (Used) and one where it is being used for a last operand (Last).

When the pending parentheses is set, the token's Used sub-code is set. When a closing parentheses token is set as a last operand, the token's Last sub-code is set. When the pending parentheses token is no longer needed, if its Last sub-code is set, the Used sub-code will be cleared, otherwise the token will be deleted. If the pending parentheses is added to the output, its Used sub-code will be left set to prevent it from getting deleted. Similarly, when a closing parentheses token is no longer needed as a last operand, if its Used sub-code is set, its Last sub-code will be cleared, otherwise the token will be deleted.

In the closing parentheses handler, when a closing parentheses is processed for a parenthetical expression, the opening parentheses (previously deleted) will now be set as the first operand and the closing parentheses (also set to the pending parentheses) will not be set as the last operand of the token on top of the done stack. The closing parentheses token's Last and Used sub-codes will be set.

Translator – First/Last Operand – Parentheses

Previously it was thought that parentheses could be ignored for the first and last operands because parentheses are always valid in a numeric expression or a string expression, though parentheses would be strange in string expression since there is currently only one string operator (concatenate), but still valid. However, consider this statement:

Z$ = A$ + -(B+C)

The entire -(B+C) sub-expression should be reported as an “expecting string expression” error. However, only the B+C is being reported before the unary operator fix and -(B+C after this fix. In both cases, the C was the last operand of the negate (where the expression type was invalid). The parentheses were removed. Had the statement been:

Z$ = A$ + INT(B+C)

The error would have been correctly reported since the closing parentheses is being attached to the last operand of the function. Therefore, both the open and closing parentheses also need to be carried through the operands.

Currently, when a closing parentheses is processed, the open parentheses token is deleted and the closing parentheses is temporarily saved in the pending parentheses variable, which is checked later to see if it was necessary or not (the parentheses sub-code of the previous operand is set if the parentheses were unnecessary). To be continued...

Translator – First/Last Operand – Unary Operators

Expression type errors involving unary operators were not pointing to the correct tokens.  This was caused because no operands were being attached to unary operators pushed to the done stack. Consider this statement:

Z$ = A$ + -B

The -B tokens should be reported as an “expecting string expression” error. However, only the B token was being reported because the first and last operand of the negate operator was being set to the first and last operand of its operand from the done stack, which was the B token.

The solution was to only attach the last operand from the operand popped from the done stack and leaving the first operand set to nothing of the unary operator token, which will cause the code to use the negate token itself as the first operand.

Translator – First/Last Operand – Initial Debugging

Initially, all the Translator tests were failing. The source of the crash was the new delete close parentheses routine, which also needed to check if the token type has a table entry. The crash occurred because when token didn't have a table entry as it was trying to access the table entry to check for a close parentheses code.

Next, a very old bug that went undiscovered was occurring in the expression only test mode used for the first four Translator tests. The problem was that the final result was left on the done stack and the Null token was left on the hold stack. The crash occurred  on the first error test when the cleanup routine was called and it tried checking for a close parentheses in the last operand – the token if was checking no longer existed. The End-of-line handler was modified to cleanup the stacks in expression mode and to check to make sure that there is only the result item on the done stack.

A series of problems were then discovered relating to unary operators and parenthetical expressions. Also, a realization was made that the first and last operands need to be saved for operands of arrays and used functions so that the Encoder can report errors correctly for array subscripts and function arguments. More on these problems to follow...

Translator – First/Last Operand Implementation

As the hold stack was being changed from holding just a token pointer to a structure containing a token, a first operand token and last operand token pointers, it was noticed that the end of the Operator and Equal (for the equality operator) token handlers contained almost identical code, both needing modified for the hold stack item change. The code was moved and replaced with a call to a new process first operand routine.

A second token pointer argument was add to the process final operand routine, which is called to add a token to the output list by the add operator routine (to add an operator from the hold stack), add print code routine (to add a hidden print code for a specific data type), and the close parentheses token handler (to add a function or array from the hold stack). This second token pointer will contain the first operand token (from the add operator routine), nothing (from the add print code routine), or the close parentheses token (from the close parentheses token handler).

The find code routine was modified to return the first and last operand token pointers from the operand on the done stack that is being checked. These arguments are pointers to token pointers with a null pointer default value – a caller only passes these when it needs them. The find code routine contains local pointer variables if the caller doesn't pass pointers since first and last operand tokens will be needed if an error occurs.

The line in the close parentheses token handler that deletes the close parentheses token was removed (since this token is now being passed to the process final operand routine to be stored temporarily as the last token pointer for arrays and functions). Several locations need to delete this token when it is no longer needed. This procedure first needs to check if the last operand token pointer is set, if the token is a close parentheses token, and then needs to delete the token. A new delete close parentheses inline function was implemented that performs this procedure.

Finally, a through inline function was implemented in the Token class that takes a second token argument and calculates the total length for a token that includes up through to this second token as described here and returns a pointer to the first token so that it can be conveniently assigned to the token being returned.  Now for debugging and testing...

Translator – Sub-String Functions

Sub-string functions add a wrinkle to storing the first and last token because these are not actually stored on the done stack (their string operand is kept on the stack). Consider this statement:

Z$= LEFT$(A$, 1) + B$ > C$

When the +$ token is processed, the operand on the stack will be A$ left there by the LEFT$( function, which will be considered the first operand of the +$ token. This would then be passed on as the first operand of the >$ token. When the error is reported, the range will incorrectly be from A$ to C$ instead of LEFT$( to C$.

To resolve this, when a sub-string function is processed (popped from the hold stack and added to the output list, but not put on the done stack where its string operand remains), the sub-string token will be put into its operand's first token on the done stack. If this token already has a first token, it will be overwritten.

In the statement above, the first operand of A$ will be set to the LEFT$( token. The +$ token will then inherit the LEFT$( as its first token, followed by the >$ token. When the error is finally reported, the range of tokens will correctly be from LEFT$( to C$. Now on to the implementation of the first and last operand...