CS3203 Team 11 Documentation

# CS3203 Team 11 Documentation [TOC] # Scope of Prototype Implementation ## Product Specifications The prototype has been built to meet the requirements described in Iteration 1 (Basic SPA/PQL). The Front End validates a single-procedure SIMPLE program in accordance to its Concrete Syntax Grammar, afterwhich a semantic check will be done. Then, the Design Processor and Design Extractor components would populate the Program Knowledge Base. The Program Knowledge Base (PKB) contains tables required for the following relationships: Follows, Follows*, Parent, Parent*, Uses, Modifies, and pattern, as needed. The Processing Query Language (PQL) Processor, like the Front End, validates a query based on the PQL grammar and performs a semantic check. The validated query will then be evaluated by obtaining relevant information from the PKB before deriving an answer. ## Bonus Functionalities (Iteration 1) Besides fulfilling the full specifications for Basic SPA/PQL, our team also implemented the following bonus functionalities: * Ability to parse and evaluate PQL queries with multiple constraint clauses * Multiple such-that and pattern clauses * eg. `Select a1 such that Follows(a1,a2) such that Follows(a2,w)`) * Multiple `and` linked constraints within each such-that/pattern clause * eg. `Select a2 pattern a2(v,_) and a1(v,_"x"_)` * Ability to evaluate and project PQL queries that specify a tuple output * eg. `variable v; while w; if ifs; Select <v,w,ifs>` * Ability to tokenize, validate, and extract semantic information from mathematical expressions for the full SPA requirements (both PQL and SPA) * eg. `x = x % 3 + ((5+2) * (2-1)) + 3` * Ability to evaluate the full SPA requirements for the assignment pattern (both exact matching and partial matching of expressions): * expression-spec : ‘"‘ expr’"’ | ‘\_’ ‘"’ expr ‘"’ ‘\_’ | ‘\_’ * eg. `Select v pattern a(_, _"x%3+((5+2)*(2-1))"_)` ## Development Plan **Timeline (Organised by components)** The table below highlights the development timeline of our group, split into weeks, with each week being a mini-iteration. **Timeline (Organised by team members)** The table below is variation of the previous table but split by each team member's responsibility in each week. The bulleted list(s) within in each cell represents the activity related to its relevant task. The timeline was decided as follow: <table> <tr> <td rowspan="2";align="center">Team Member</th> <td colspan="5";align="center">Week</th> </tr> <tr> <td align="center">2 20 Jan 2020 - 27 Jan 2020</td> <td align="center">3 28 Jan 2020 - 03 Feb 2020</td> <td align="center">4 04 Feb 2020 - 10 Feb 2020</td> <td align="center">5 11 Feb 2020 - 17 Feb 2020</td> <td align="center">6 (Back Up Week) 18 Feb 2020 - 21 Feb 2020</td> </tr> <tr> <td>Eric</td> <td rowspan="6">Admin <ul> <li>Administrative setup</li> <li>Understanding Project Requirements</li> <li>Understanding Iteration 1 Deliverables</li> <li>Discussion of Implementation Designs</li> <li>Role Allocation</li> </ul> </td> <td>Testing <ul> <li>Draft 1 for test cases</li> </ul> </td> <td>FrontEnd <ul> <li>FrontEndSemanticExtractor</li> </ul> Testing <ul> <li>Unit Tests</li> <li>Refine test cases draft</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>Testing <ul> <li>System Tests</li> </ul> Admin <ul> <li>Group Report</li> </ul> </td> <td rowspan="6">Testing <ul> <li>Refine System Tests</li> </ul> Admin <ul> <li>Refine Group Report</li> <li>Refine Code</li> </ul> </tr> <tr> <td>Jason</td> <td>PQL <ul> <li>Analyse and explore query evaluating methods</li> </ul></td> <td>PQL <ul> <li>Evaluator</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>PQL <ul> <li>Evaluator</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> <li>Group Report</li> </ul> </td> </tr> <tr> <td>Jonathan</td> <td>PKB <ul> <li>PKB</li> </ul> Commons <ul> <li>Shared Utils</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>PKB <ul> <li>PKB</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>Testing <ul> <li>Integration Tests</li> <li>System Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> </tr> <tr> <td>Kok Yuan</td> <td>FrontEnd <ul> <li>DesignExtractor</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>FrontEnd <ul> <li>DesignExtractor</li> </ul> PKB <ul> <li>PKB</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>Testing <ul> <li>Integration Tests</li> <li>System Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> </tr> <tr> <td>Terence</td> <td>FrontEnd <ul> <li>FrontEndTokenizer</li> <li>FrondEndSyntaxChecker</li> </ul> Commons <ul> <li>Shared Utils</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>FrontEnd <ul> <li>FrontEndDesignProcessor</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>Testing <ul> <li>Integration Tests</li> </ul>Admin <ul> <li>Group Report</li> </ul> </td> </tr> <tr> <td>Yong Kuan</td> <td>PQL <ul> <li>PQLTokenizer</li> <li>PQLSyntaxChecker</li> </ul> Commons <ul> <li>Error Handlers</li> <li>Shared Utils</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>PQL <ul> <li>PQLSemanticChecker</li> <li>Query</li> </ul> Testing <ul> <li>Unit Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> <td>Testing <ul> <li>Integration Tests</li> <li>System Tests</li> </ul> Admin <ul> <li>Documentation</li> </ul> </td> </tr> </table> ### Week 2 This week was mainly used to set up the project and for each of us to familarise with the code base of this project. Communication channels were also set up in Telegram and Slack. We also made use of this week before consulations began to do a rough sketch on how to develop our solution, without actually implementing it. We began discussions of each of our individual's strengths and weakness so as to facilitate the assignmment of roles best fitted to on each individual's skills and preference. Then, we decided on the mini-iteration format that we will take, as described in this development plan, such that each week ends on the day before our consultation with Dr Cristina (every Tuesday). We also decided on weekly group meetings, 2 hours before consultation, to update on our progress and make changes to our development plan is necessary. ### Week 3 In the first mini-iteration, we planned to develop utility methods (SharedSyntaxUtil, FileOpener) and constants (SPAConstants) that needed to be defined, so there will not be a repetition of work between developers in later stages. This will prove important to standardise how we want to name common keywords that will be used in most, if not all, components, i.e. statement keywords. Basic syntax and semantic error handlers were implemented in this week for the parser and preprocessing developers to use later in the week. After the utility and shared functions were up, we took the rest of the week to fully develop the components that had specification laid out in detail, i.e. the parsers and preprocessors with the respective grammars well-defined in the CS3203 Wiki page. PKB would begin design considerations for data structures used for the tables to store information. Also, initial implementations began to give more buffer time for Week 2's deadline. The Evaluator on the other hand, was of fairly complex and it is not a high priority in the first week, so time was given to properly analyse how to evaluate queries and the various ways it can be achieved. ### Week 4 In the second mini-iteration, components from Week 1's implementations were developed further, notable the FrontEndParser and PQLPreprocessor tasks. Semantic checks were implemented to complement the syntax checkers. Also, the FrontEndDesignProcessor and DesignExtractor began implementations to facilitate the "connection" between the FrontEnd and PKB. PKB at this stage, had its data structure designs firmed up and adjusted based on consultation with Dr. Cristina, and was thus its API was fully completed just before FrontEndDesignProcessor and DesignExtractor were implemented. The Query and Evaluator began to finalise their initial implementaion. We had intended for the Evaluator to be be finished by the end of this week, but the consultation with Dr. Cristina revealed some loopholes in the approach we took when it came to evaluating queries. We adjusted our timeline to give the Evaluator more time for completion. At the same time, components that had finished their implementations began on Unit Testing to test for bugs, before System Tests and Integration Tests were scheduled to begin in Week 5. ### Week 5 In this third mini-iteration, we planned to do extensive testing on the different components. At this stage, we had already done unit testing for most of the components and started to design system and integration tests. The lesson on Testing had given us advice on how to better plan for test cases and this contributed to bugs in implementation that we initially had not realised. As such, certain components are tweaked to address these bugs. ### Week 6 This final mini-iteration was more of a back-up week for us to complete our documentation, to perform last minute integration tests and to do some minor finishing touches on the code. This was to give up some assurance that our project will not be rushed near end of the deadline, which can potentially give rise to bugs. # SPA Design ## Overview ![](https://i.imgur.com/UmmeAvh.png) The architecture diagram above shows the design of SPA and how its components are interconnected. The main SPA components are the User Interface (UI), SPAFrontEnd, Program Knowledge Base (PKB), PQLProcessor and Commons. The SPAFrontEnd can be broken down into sub-components SPAParser and DesignExtractor. The PQLProcessor can be broken down into sub-components PQLPreprocessor and PQLEvaluator. UI: The UI of the application. Used for input of the SIMPLE source program and PQL queries and displaying of results of the PQL queries. SPAFrontEnd: The SPAFrontEnd is used to validate the SIMPLE program input from UI and extract design abstractions to be stored in the PKB. FrontEndParser: The SPAParser parses and validates the syntax of the SIMPLE program while extracting basic design abstractions such as Follows and Parent. Design Extractor: The Design Extractor extracts more complex design abstractions such as Follows* and Parent* based on the basic abstractions obtained by SPAParser. PKB: The PKB is used to store design abstractions. It also contains basic information about the input SIMPLE program such as variable and procedure names, statement type etc. PQLProcessor: The PQLProcessor is used to validate the PQL queries from UI and evaluate them based on what is stored in the PKB. PQLPreprocessor: The PQLPreprocessor parses and validates the syntax of the PQL queries while extracting information to be used by the PQLEvaluator such as clause type, arguments etc. PQLEvaluator: The PQLEvaluator evaluates queries by deciding what data to get from the PKB and joining the results. Commons: Commons contains utility classes and constants that are used by multiple other components. ### Component Interactions ![](https://i.imgur.com/4G3SBrs.png) The sequence diagram above summarizes the main interactions between components. This diagram was useful in project planning and communication as it helped us to figure out which components had to work together and helped us decide what APIs were necessary. #### UI → SPAFrontEnd & PQLProcessor The UI interacts with the SPAFrontEnd and PQLProcessor when it passes user input and receives query results. SPAFrontEnd and PQLProcessor provides APIs for parsing and evaluation (respectively) to be called by UI. To simplify the API, both the SPAFrontend and PQLProcessor provides only one main driver method each - `parse()` and `evaluateQuery()`. Alternatively, the SPA can also be run using the provided `AutoTester`, which takes in two different `.txt` files containing the SIMPLE source code and PQL queries. #### SPAFrontEnd → PKB The SPAFrontEnd parser interacts with the PKB during the parsing of SIMPLE source program. The PKB provides a set of front-end specific APIs for the SPAParser to insert information on each of the basic design abstractions. As a simple example, given the following SIMPLE snippet: ``` 2. if (x == 6) { 3. while (x == 5) { 4. a = x + 5; 5. x = v + 5; } } ``` The SPAFrontEnd Parser calls the following methods from the PKB when parsing statement #5: 1. **Statement Insertion**: `insertStmtTable(5, ASSIGN)` 2. **Variables/Constants Insertion**: `insertVarTable("v")`, `insertVarTable("x")`, and `insertConstantTable(5, 3)` 3. **Basic Design Extraction** * Extract Modifies: `insertModifiesTable(5, "x")` * Extract Uses: `insertUsesTable(5, "v")` * Extract Follows: `insertFollowsTable(4, 5)` * Extract Parents: `insertParentTable(3, 5)` The FrontEnd thus interact directly with the PKB API during parsing to insert basic design patterns, and populate other semantic information like variables or constants used. After parsing, the FrontEnd then invokes the DesignExtractor to identify the more complex design abstractions from the inserted elements in the PKB, eg. from the above code example, extracting the `Parent*` relationship between #2 and #5 from their corresponding `Parent` entries. #### PQLProcessor → PKB The PQLProcessor interacts with the PKB during the evaluation of PQL queries. The PKB had to provide APIs for the PQLProcessor to get the information stored on each of the design abstractions. ## Design of SPA Components - Commons - SPAFrontEnd - PKB - PQLProcessor ## Commons Classes/Constants ### Common `enums`, literals, and lookup tables In the SPA, several constants, tables, and `enum` classes are used by across different software components. These include, but are not limited to: * Special SIMPLE symbols (eg. `{`, `}` etc.) * Special PQL symbols (eg. `_`, `,` etc.) * SIMPLE Design Entities (eg. `if`, `while` etc. ) * PQL Design Entities ( eg.`stmt`, `assign` etc.) * Relationship Types (eg. `Follows`, `FollowsStar`) * Getter methods for `std::string` literal representation of the above. storing in namespace vs storing in static class vs defining in each header file individually vs using string !!! TABLE OF DESIGN CONSIDERATIONS GOES HERE !!! ### SPA Exception Handling The static program analyzer encounters two main types of exceptions during its exceution. They are defined as follows: * `SyntaxError`: Source code (SIMPLE or PQL) that directly violates the concrete syntax grammar as defined in the specifications. Examples of these are missing braces or illegal variable names. * `SemanticError`: Source code (SIMPLE or PQL) that adheres to the concrete grammar syntax, but is however contextually invalid for successful program/query execution. This includes mistakes like undeclared variables or illegal synonym types for a specific clause. Since such errors are common to nearly all the components of the SPA, they were standardized early on in the development phase as custom exception classes extended from `std::exception`. A simple class diagram with shown dependencies can be seen as follows: !!!! class diagram !!!!! ## SPAFrontEnd The SPAFrontEnd processes the source code input. It comprises two sub-components: FrontEndParser and DesignExtractor. The sequence diagram below shows how the two sub-components interact to process a source code that is given as input. ![](https://i.imgur.com/vQNTJAN.png) ### FrontEndParser The FrontEndParser tokenizes the source code input, and then validates the tokens in terms of validity and semantics. Validity is defined by SIMPLE language's Concrete Grammar Syntax (CGS). Semantics is defined by the following rules: - No recursive calls - No call to procedures that don't exist - No duplicate procedure names The sequence diagram below shows how the FrontEndParser parses a source code. ![](https://i.imgur.com/27u6CPH.png) The **FrontEndTokenizer** is invoked first, by tokenizing the string sourceCode input into tokens. A `istringstream` is used to iterate through the string character by character. A stream is used instead of a character array because the size is not required to be known. The sourceCode is tokenized by using white-space (as defined in 'C' locale) as 'separators'. The following can be seen as rules to how the tokenizing is done: - If a character inside a set of symbols used in SIMPLE CGS ("Special symbols") is found, it is added to the vector as a token. - If a non-special symbol or non-white-space character is found, add this character to an accumulator. - If a white-space charcater is found, add whatever is in the accumulator as a token. If accumulator is empty, skip to the next character. A white-space defined in 'C' locale is as follow: <style type="text/css"> .tg {border-collapse:collapse;border-spacing:0;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-mqa1{font-weight:bold;border-color:#000000;text-align:center;vertical-align:top} .tg .tg-73oq{border-color:#000000;text-align:left;vertical-align:top} </style> <center> <table class="tg"; align='center'> <tr> <th class="tg-mqa1">char</th> <th class="tg-mqa1">Hex</th> <th class="tg-mqa1">Description</th> </tr> <tr> <td class="tg-73oq">’ ’</td> <td class="tg-73oq">(0x20)</td> <td class="tg-73oq">Space (SPC)</td> </tr> <tr> <td class="tg-73oq">‘\t’</td> <td class="tg-73oq">(0x09)</td> <td class="tg-73oq">Horizontal Tab (TAB)</td> </tr> <tr> <td class="tg-73oq">‘\n’</td> <td class="tg-73oq">(0x0a)</td> <td class="tg-73oq">Newline (LF)</td> </tr> <tr> <td class="tg-73oq">‘\v’</td> <td class="tg-73oq">(0x0b)</td> <td class="tg-73oq">Vertical Tab (VT)</td> </tr> <tr> <td class="tg-73oq">‘\f’</td> <td class="tg-73oq">(0x0c)</td> <td class="tg-73oq">Feed (FF)</td> </tr> <tr> <td class="tg-73oq">‘\r’</td> <td class="tg-73oq">(0x0d)</td> <td class="tg-73oq">Carriage Return (CR)</td> </tr> </table> </center> After tokenizing, the **FrontEndSyntaxChecker** gets invoked. a Top Down parsing implementation is used, specifically the Resursive Descent. Two version of Recursive Descent has been implemented: Back-Tracking and LL. Back-Tracking was used throughout the parsing, except for when parsing `expr`. Because of the left recursive definition of `expr` in the CSG, Back-Tracking would be very hard to implement. As such, we opted to rewrite the definition to LL(1) grammar, and perform a LL parse. A comparison of the original and rewritten grammar is as follow: <style type="text/css"> .tg {border-collapse:collapse;border-spacing:0;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-18eh{font-weight:bold;border-color:#000000;text-align:center;vertical-align:middle} .tg .tg-mqa1{font-weight:bold;border-color:#000000;text-align:center;vertical-align:top} .tg .tg-0a7q{border-color:#000000;text-align:left;vertical-align:middle} .tg .tg-73oq{border-color:#000000;text-align:left;vertical-align:top} </style> <table class="tg"> <tr> <th class="tg-18eh" colspan="2">Original Left Recursive Grammar</th> <th class="tg-mqa1" colspan="2">Rewritten LL(1) Grammar</th> </tr> <tr> <td class="tg-0a7q" rowspan="3">expr ::= </td> <td class="tg-73oq">expr '+' term |</td> <td class="tg-73oq">expr ::=</td> <td class="tg-73oq">term exprTail</td> </tr> <tr> <td class="tg-73oq">expr '-' term |</td> <td class="tg-73oq" rowspan="3">exprTail :=</td> <td class="tg-73oq"><Empty> |</td> </tr> <tr> <td class="tg-73oq">term</td> <td class="tg-73oq">'+' term exprTail |</td> </tr> <tr> <td class="tg-73oq" rowspan="3">term ::=</td> <td class="tg-73oq">term '*' factor |</td> <td class="tg-73oq">'-' term exprTail</td> </tr> <tr> <td class="tg-73oq">term '/' factor |</td> <td class="tg-73oq">term ::=</td> <td class="tg-73oq">factor termTail</td> </tr> <tr> <td class="tg-73oq">term '%' factor |</td> <td class="tg-73oq" rowspan="4">termTail</td> <td class="tg-73oq"><Empty> |</td> </tr> <tr> <td class="tg-73oq" rowspan="3">factor ::=</td> <td class="tg-73oq">varName |</td> <td class="tg-73oq">'*' factor termTail |</td> </tr> <tr> <td class="tg-73oq">constValue |</td> <td class="tg-73oq">'/' factor termTail |</td> </tr> <tr> <td class="tg-73oq">'(' expr ')'</td> <td class="tg-73oq">'%' factor termTail</td> </tr> <tr> <td class="tg-73oq" colspan="2" rowspan="2">where varName and constValue are terminals</td> <td class="tg-73oq">factor ::=</td> <td class="tg-73oq">No change to original grammar</td> </tr> <tr> <td class="tg-73oq" colspan="2">where varName and constValue are terminals</td> </tr> </table> In general, the keywords `procedure`, `read`, `print`, `call`, `if`, `while` are used to determine which statement grammar is to be used. However, an interesting thing to note is that keywords can be variable names, so statements like `while = while + 1` is valid. Under the explanation above, this example would have been checked under the `while` grammar even though it should be checked under the `assign` grammar. To deal with such cases, when determining which statement grammar to use, FrontEndSyntaxChecker checks if the token following the keyword is a `=` token or not. If it is, the `assign` grammar will be used. Else, the `while` grammar will be used instead. Next, the **FrontEndSemanticChecker** gets invoked. The FrontEndSemanticChecker checks the tokenised code against the semantic requirements. It ensures that there are no: * Duplicate procedure/variable names * Call invalid procedure name * No recursive procedure calls * No cyclic procedure calls To achieve semantic correctness, a table of unique procedure names are generated. Duplicate procedure names will throw an error. There is no need to check for duplicate variable names as there are no variable declarations in SIMPLE. Calls made are also noted down. If there is a call to a procedure name not found in the table of unique procedure names, an error will be thrown. Depth-frist search is used to detect recursive and cyclic calls in the SIMPLE program. If the tokenised source passes all the test, the source is deemed semantically correct and passed to the Design Processor. Lastly, the **FrontEndDesignProcessor** gets invoked. It does a first level of design extraction by extracing the abstractions that can be directly obtained in one parse through the validated code, i.e. Uses, Modifies, Parent and Follows. It also stored relevant information into the PKB, namely the Procedure Statement Table, Statement Table, Variable Table, Constant Table and Full Assign Expression Table. These tables are part of the PKB and will be further elaborated later in this report. It works by processing 7 main types of statements/containers, mainly `procedure`, `read`, `print`, `call`, `if`, `while` and `assign`. The single-lined statement types, i.e. `read`, `print`, `call` and `assign` are processed until a `;` is found, where relevant tables gets stored while scanning. The container-typed statements, i.e. `procedure`, `if` and 'while' are processed implicitly like stack frames to deal with nesting. The following explanation attempts to use some Operating Systems jargon to depict how processing is performed for containers. Each container is treated as a separate stack frame, and within it, statements are processed one by one as aforementioned and stops when a `}` is found. If a container (`if` or `while` only) is found within the frame, another frame will be created to process the inner frame. To handle proper insertion to the Parent Table with nesting, a local variable `parentStmtNum` to holding parent statement number is passed into every stack frame and every statement inside it uses the local parent statement number to populate the Parent Table. To handle proper insertion to the Follows Table with nesting, a global variable `precedStmtNum` holding a preceding statement number is used: - Without nesting, `precedStmtNum` gets updated after every statement (by assigning it with its own statemet number), which is to be used by the next statement. - However, this becomes tricky because a statement number at the end of a container should not Follow the next statement, but instead the statement with the `if` or `while` keyword should be the one which `Follow`s the next statement. To deal with this, `precedStmtNum` gets updated at the end of processing a container statement to the `while` or `if` statements number, which is to be used by the statement AFTER the container. **Alternative solutions:** multiple-pass parsing vs single-pass regex vs pure recursive descent ### DesignExtractor The DesignExtractor uses the design abstractions stored in the PKB by the SPAFrontEnd to extract more complex relationships in the source code. Namely, Parent* and Follows* relationships, and Uses and Modifies relationships within nested container statements. The DesignExtractor has one public API which is called by the UI. This API call tells the DesignExtractor to begin extracting the complex relationships, and store them back in the PKB. The complex abstractions are derived from the existing design abstractions as follow: - Follows* is derived from Follows. - Parent* is derived from Parent. - Nested Uses is derived from Parent and Uses. - Nested Modifies is derived from Parent and Modifies. The sequence diagram below shows an example of how the DesignExtractor interacts with the PKB. ![](https://i.imgur.com/aatvqF5.png) In the above example, the SPAFrontEnd calls `extractDesigns()` to the DesignExtractor. The DesignExtractor will get the PKB instance, then call `extractFollowsStar()`. Looping through the statement numbers backwards, for each statement number, the DesignExtractor gets from the PKB the statement that follows the current statement, called `follower`. If it exists, the DesignExtractor inserts the statement and its `follower` into the `followsStarTable` in the PKB. Then, the DesignExtractor gets the set of `followerStar` of the `follower`, and adds the current statement and any element in that set to the `followsStarTable` in the PKB. ## PKB design **Overview of PKB Design** The PKB provides storing functionality for the Parser and Design Extractor. It also provides retrieval functionality for the Query evaluator for the data stored by the Parser and Design Extractor. **Component Interactions involving PKB** The interactions between the Parser/Design Extractor and the PKB and the PKB and Query Evaluator are shown in the [Component Interactions](#Component-Interactions) section. **Current PKB Design Structure** Procedure and Variable Table (Vector data structure) Vector data structure is used to allow working with index for other data structures which stores procedures and variables. This is beneficial for data structures such as unordered map which are used in other tables as hashing of procedure names or variables names which are strings are generally more expensive compared to hashing of index which are integer data type. Complexity: * Amortised O(1) time complexity for appending new procedure or variables to the vector data structure. * O(1) time complexity for the retrieval of procedure or variable via their corresponding index. * Space complexity is O(n) where n is the number of procedures or variables stored in their respectively vector data structure. Some examples of the table structure: <style type="text/css"> .tg {border-collapse:collapse;border-spacing:0;float:left} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-c3ow{border-color:inherit;text-align:center;vertical-align:top} </style> <table class="tg"> <tr> <th class="tg-c3ow">VARINDEX</th> <th class="tg-c3ow">VARNAME</th> </tr> <tr> <td class="tg-c3ow">0</td> <td class="tg-c3ow">A</td> </tr> <tr> <td class="tg-c3ow">1</td> <td class="tg-c3ow">B</td> </tr> </table> <style type="text/css"> .tg {border-collapse:collapse;border-spacing:0;float:center} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-c3ow{border-color:inherit;text-align:center;vertical-align:top} </style> <table class="tg"> <tr> <th class="tg-c3ow">PROCINDEX</th> <th class="tg-c3ow">PROCNAME</th> </tr> <tr> <td class="tg-c3ow">0</td> <td class="tg-c3ow">procedure1</td> </tr> <tr> <td class="tg-c3ow">1</td> <td class="tg-c3ow">procedure2</td> </tr> </table> Follows Table (unordered map data structure with one to one mapping) Complexity: * O(1) insertion, search and retrieval operations. * For each of the tables above, there are corresponding reverse tables and pair tables (for design abstraction relationships) to reduce the time complexity of searching by taking advantage of unordered maps data structure which has amortised O(1) search operation through the use of hash tables. **Design Problem:** A design is required to access and retrieve stored variables and procedures from their respective data structures quickly and efficiently. **When it is used:** Accessing and Retrieving 1. Variables 2. Procedures **Alternative solutions:** 1. Vector data structure can be used to store variables and procedures. * Pros: O(1) time complexity in accessing and retrieving elements via index. * Cons: The underlying data structure allows for duplicate elements and searching an element in vector requires O(n) time complexity. 2. An unordered set data structure can be usoed to store variables and procedures. * Pros: Access and retrieval of elements are generally O(1) time operations as it underlying implementation involves using hashing. In addition, no duplicates are allowed in unordered set data structure compared to in vector. * Cons: Hashing of variables and procedures which are of string data type is expensive and may result in accessing of elements to be more than O(1) time complexity compared to accessing via index in vector. **Criteria requirements** 1. Fast and efficient access and retrieval of stored variables and procedures. 2. There should be no duplicate variable names or duplicate procedure names (Additional rules in Basic + Advanced SPA Requirement). **Decision and Justification** The vector data structures are used to store variables and procedures respectively due to the O(1) time access and retrieval operations via index. The cons of having duplicate elements and expensive search operation in a vector can be resolved by constructing an unordered map where the element in the vector is the key while the corresponding value is the index in the vector. Taking advantage of the underlying hash table implementation of an unordered map, there would be no duplicate keys hence, no duplicate elements in the vector if we check if the element exists as a key in the unordered map, and if it exists, the element is not inserted into the vector otherwise, it is inserted into the vector and the unordered map. This results in no duplicate elements, O(1) access and retrieval of elements via index and slightly more than O(1) search of the elements without index due to hashing which is a good compromise and meets the criterias mentioned above. **Design Problem:** A design is required to access and retrieve a list of elements from an input. **When it is used:** Accessing and Retrieving 1. Constants from statement number 2. Procedures from statement number 3. Statement numbers from statement type 4. Parent/Parent*/Follows*/Modifies/Uses design abstraction relationship 5. Statement numbers from full/partial Assignment expression 6. Follows design abstraction relationship (however, it does not require mapping to a list of elements and just map to another statement number due to the properties of Follows design abstraction relationship) **Alternative solutions:** 1. An unordered map data structure where the key is mapped to an unordered set (value). * Pros: O(1) time insert and search operations as the underlying implementation of an unordered map is a hash table. The unordered set in which the key is map to, also has an underlying implementation of a hash table hence, it also has search operation of O(1) time. This results in the overall search operation to be around O(1) time. In addition, an unordered set (value) does not allow duplicates. It is also less complex to implement and easier to understand. * Cons: There is a larger memory requirement due to multiple redundancies needed. For example, in a Parent design abstraction relationship, an unordered map is needed to map parent statement number to an unordered set of child statement numbers. At the same time, another unordered map is needed to map the child statement number to an unordered set of parent statement number. This is to allow for O(1) time retrieval for input parent statement number or input child statement number. 2. An Abstract Syntax Tree (AST) can be implemented following the SPA concrete syntax grammar (CSG). * Pros: All the design abstraction relationships can be retrieved from a single AST. * Cons: Implementation is complex and in depth knowledge is required on implementing an AST. Furthermore, the depth first search traversal of the AST takes O(V + E) time complexity where V is the number of vertices/nodes in the AST and E is the number of edges in the AST which is slow hence, performance would be greatly affected. It is also difficult to extend the implementaton of the AST for further iterations due to its complexity. **Criteria requirements** 1. Fast and efficient access and retrieval of the corresponding list of elements from an input. **Decision and Justification** The unordered map data structure with the key map to an unordered set data structure (value) is used due to the easier implementation, easier understandability for new developers, faster search and retrieval operation compared to an AST. Although, multiple redundancies are required, the trading of space for time makes it suitable given that the specifications require for fast evaluation. ## PQL Processor The PQLProcessor evaluates PQL queries. It comprises two sub-components: the PQLPreprocessor, and the PQLEvaluator. These components communicate indirectly via a `Query` class. The sequence diagram below shows how the two sub-components interact to evaluate a query. ![](https://i.imgur.com/cxhKjBR.png) ![](https://i.imgur.com/mViUFZZ.png) ### PQL Preprocessor Before the query string can be evaluated, it is first passed to the `PQLPreprocessor`, which acts as the driver class for entire sub-component, and makes API calls to `PQLTokenizer`, `PQLSyntaxChecker`, and `PQLSemanticExtractor`, in that order. Together, they are responsible for the following: * `PQLTokenizer`: Tokenization of the query string according to special PQL language symbols, along with removal of all whitespace characters. Returns a vector of tokens. * `PQLSyntaxChecker`: Validates query syntax according to the defined PQL concrete grammar. If syntax is invalid, returns false. The `PQLPreprocessor` will then halt the entire evaluation process by throwing a `SyntaxError`. * `PQLSemanticExtractor`: * If semantic rules are violated (eg. undeclared variables), halts entire process by throwing a `SemanticError`. * Extracts the necessary semantic information (declarations, result clauses, constraint clauses) from the given tokens, and returns a `Query` object on success. The `Query` object is guaranteed to be non-trivial and semantically valid. A sequence diagram is shown below to further illustrate the interactions between each of these classes: ![](https://i.imgur.com/ZFPevKi.png) #### Design of `PQLTokenizer` and `PQLSyntaxChecker` It should be noted that although SIMPLE and PQL are two distinct languages, they are both LL grammars that can be (mostly) tackled using left-to-right recursive descent. To maintain parsing consistency within the SPA program, we opted to synchronize design decisions between the two components during implementation and planning. The design of `PQLTokenizer` and `PQLSyntaxChecker` is hence analogous to that of the `SPATokenizer` and the `SPASyntaxChecker` respectively, with the exception that a different set of rules (PQL concrete grammar) and symbols (PQL symbols) were used for parsing instead. Refer to the `FrontEnd` parsing section above for the joint design decisions made for parsing. #### Design of `PQLSemanticExtractor` ##### Semantic Validation One notable aspect of the PQLSemanticExtractor is that it has to semantically validate a large amount of relationships, along with the types of allowed arguments, which can differ based on the type of relationship given. The amount of relationships is projected grow even larger in the full SPA (iteration 2). To increase the maintainability of the validation process for iteration 2, a Table-Driven-Design approach was used to implement semantic validation, thus separating the program logic from the lookup parameters (valid argument types). The high-level diagram below shows an overview of the tables used for validating iteration 1 relationships: ![](https://i.imgur.com/gGHcPu3.png) For example, when parsing the such-that clause for the following example: ``` procedure p; variable v; Select v such that Uses(p, v) ``` 1. The `PQLSemanticExtractor` first infers the relationship type from the keyword (and in the case of UsesP, additional contextual cues from the LHS argument). 2. Thereafter, it looks up `UsesP` in the `LEGAL_RELATIONSHIPS` table, and obtains the entries `PROC_REF` (LHS), and `VAR_REF` (RHS). Internally, the table is implemented as a hash table of enums to a pair of sets. 3. Having obtained these two entry references, it then looks up the different allowable types under `PROC_REF` and `VAR_REF` , and checks these against the synonyms `p` and `v` in the query above. Internally, `PROC_REF` and `VAR_REF` is implemented as an hash set of enums. 4. Since the synonyms `p` and `v` have types that belong to the valid table entries, the clause passes the semantic validation check, and it is added to the `Query` object. ##### Preprocessing Optimizations In certain exceptional cases, even though a clause may be valid (in terms of the defined PQL grammar and usage), it may always trivially evaluate to have no results regardless of the SIMPLE source code given. We call such clauses "trivially false-evaluating" clauses. To prevent unnecessary computation on such queries (especially on the other clauses), these are identified as semantic errors during semantic extraction in the preprocessing stage (`PQLSemanticExtractor`) so that the entire evaluation process is halted. Some of these are built into the Table-Driven-Design covered in the previous section (eg. `print` synonyms are considered to be a semantically invalid LHS argument for the `ModifiesS` relationship, since it will never return a result regardless of the source code). In iteration one, these are the full list of cases currently covered: * Follows/Follows*/Parent/Parent*: when the RHS is an integer of `1`. * Follows/Follows*/Parent/Parent*: when the LHS and RHS are equal (and are not underscores) * For all applicable relationships: when an argument is an integer of `0`. * ModifiesS, when the LHS is a synonym of type `print`. * UsesS, when the LHS is a synonym of type `read`. ### Query The Query class contains all information needed for query evaluation. Each clause of the query is represented by the `ResultCl`, `SuchThatClause` or `PatternClause` classes which stores information such as argument types and names. Below is a class diagram to better illustrate how data is organized for each query. ![](https://i.imgur.com/soiUv0g.png) We know an entity is new if its index is equal to the table size as indexes start at 0. For single values, we do a cross product of all existing combinations with all values of the new index. This is because there is no intersection between existing results and new values, therefore all combinations of the existing results and new values are valid. For pairs, we treat each pair as a single unit as combinations with the pairs apart are not allowed. Below is an example to show the scenario of adding a new entity and a new pair: ![](https://i.imgur.com/EcqWWJx.png) For existing values, we check if the value of the entity is present in both the table and the new set. To do this we use an unordered set to store the new values for efficient checking. If the value in the table is not found in the set, we can remove the column containing that value. Below is an example to show the scenario of adding an existing entity and an existing pair: ![](https://i.imgur.com/wKGzUCG.png) Lastly if half of a pair is an existing entity and half is a new entity, for each intersecting value, we cross product the column with that value with the other half of the pairs with that value. ![](https://i.imgur.com/kXzShjm.png) By doing cross product, we will always get all possible combination of values. By removing combinations that have invalid values, we always have only valid combinations in our table. When the get method is called, we simply return the vectors associated with the selected entities. Selecting a portion of the table may cause duplicated combinations. This is expected behaviour that is not handled by the ResultsTable. #### ResultsProjector Based on the selected synonyms type, the ResultsProjector first converts each result to string form. For procedure and variable type results, the ResultsProjector interacts with the PKB to get the stored string form of the result based on index. For statement type results, the int result is converted to a string using std::to_string. Based on the number of selected synonyms, the results are combined into a single string and separated by a space. As we return an unordered set of strings, we are guaranteed no duplicates. #### EvaluatorUtility The EvaluatorUtility class contains utility functions used by QueryEvaluator and Evaluator classes such as countSynonyms and intersect. ## Documentation and Coding Standards ### Standards for abstract APIs **Naming Conventions** * Variable names must be nouns and written in camelCase. * E.g. queryEvaluator, clause * Function Names must be verbs and written in camelCase. * E.g. evaluateQuery, parse * Boolean variables/functions should be named to sound like booleans. * E.g. isParent(), isValid * Plural form should be used on names representing a collection of objects. * E.g. clauses, tokens * Abbreviations and acronyms should not be uppercase when used as a part of a name. * E.g. SpaFrontEnd, PqlProcesser * All names should be written in English. **API Specification format** RETURN_TYPE name(type parameter(s))); Description: -describe what the operation does -describe both normal and abnormal behavior ### Coding Standards Adapted from: https://oss-generic.github.io/process/codingStandards/CodingStandard-Java.html https://google.github.io/styleguide/cppguide.html **(Additional) Naming Conventions** * Class/enum/namespace names must be nouns and written in PascalCase. * E.g. QueryEvaluator, Clause * Constant names must be all uppercase using underscore to separate words. * E.g. PROCEDURE_KEYWORD, UNDERSCORE * Iterator variables can be called i, j, k etc. * Underscores may be used in test method names using the following three part format featureUnderTest_testScenario_expectedBehavior() **Layout** * Basic indentation should be 4 spaces (not tabs). * Each line of text in your code should be at most 80 characters long. * Break after a comma. * Break before an operator. * Indentation for wrapped lines should be 8 spaces * Place line break to improve readability * Use K&R style brackets (aka Egyptian style). * Operators should be surrounded by a space character. * Reserved words, commas, semicolons should be followed by a white space. **if-else format** ```cpp if (condition) { doSomething(); } else if (condition) { doSomethingElse(); } else { doAnotherThing(); } ``` **switch format** ```cpp switch (condition) { case 1: doSomething(); //Fallthrough case 2: doSomethingElse(); break; default: doAnotherThing(); break; } ``` The explicit //Fallthrough comment should be included whenever there is a case statement without a break statement. **while format** ```cpp while (condition) { doSomething(); } ``` **for format** ```cpp for (initialization; condition; update) { doSomething(); } for (range_declaration : range_expression) { doSomething(); } ``` **do-while format** ```cpp do { doSomething(); } while (condition); ``` **try-catch format** ```cpp try { doSomething(); } catch (SyntaxError exception) { handleException(); } ``` **Header files** * Every .ccp file should have an associated .h file. * There are some common exceptions, such as unit tests and small `.cpp` files * Include headers in the following order: Related header, C system headers, C++ standard library headers, other libraries' headers, your project's headers. * For clarity of scope, and to reduce namespace pollution, the `using` directive should not be used in the main source code. * Avoid using forward declarations where possible. Instead, `#include` the headers you need. **Comments** * Every non-obvious class declaration should have an accompanying comment that describes what it is for and how it should be used. * Almost every function definition should have comments immediately preceding it that describe what the function does and how to use it. Comments are placed in the implementation `.cpp` files instead of the header `.h` files. This is to prevent cluttering in the `.h` file, which aids in providing a quick "bird's eye" view of all concrete API declarations within the header file. **Classes/Namespaces** * Sections in public, protected and private order, each indented. * Omit sections that would be empty. * Declarations in following order: types (including typedef, using, and nested structs and classes), constants, factory functions, constructors, assignment operators, destructor, all other methods, data members. ### Correspondence Between Abstract and Concrete API We have enhanced the correspondence between abstract APIs, and their concrete API counterparts by: * Using the same name for the functions * Use types for the parameters and return value that closely match the abstract form * E.g int for STMTNUM and string for VARNAME. * For abstract types that have no relatable C++ type, we have made enumerations to represent them * E.g ARGUMENT_TYPE is represented by the enum PQLConstants::DesignEntities. ## Testing ### Introduction A Static Program Analyzer (SPA for short) is an interactive tool that automatically answers queries about programs. The SPA is designed to be used for SIMPLE source program. The motivation behind SPA is to reduce the amount of time spent on understanding the program, easing the debugging and maintainance process. ### Objectives The objective of the test plan is to provide test cases which cover the SPA program extensively, ensuring that it meets the requirements and function as intended. The goal is to ensure that the SPA program is able process complex nested SIMPLE programs and answer complex PQL queries accurately. ### Testing Strategies ![](https://i.imgur.com/qL3h8k8.png) To handle complex SIMPLE program and complex PQL queries, the SPA developed is tested systematically. At individual level, unit testing will be conducted to ensure that individual components are working correctly. Integration testing is then conducted to ensure that the components work together properly, before system testing which checks if all the functional requirements are met. In Iteration 1, acceptance testing will not be conducted. ### Unit Testing Unit Testing is a level of software testing where individual components of a software are tested. The purpose is to validate that each unit of the software performs as designed. Unit Testing of an individual component is done by the developer of that component. For instance, a developer who is working on the Frontend SPA Semantic Checker, will be coming with unit test cases to ensure that the Semantic Checker is working correctly. In the unit testing framework, drivers and subs are often created to assist in unit testing. However, the unit testing carried out for this SPA application defined a single unit as an individual fuction. Output generated from the previous function is used as input for the unit test cases. The assumption made here is that the input generated from the previous step is accurate and had been well tested. This bottom up testing approach ensures that the components at the lower hierarchy are tested invidually before the components that rely upon them are tested. This approach also ensure that the input given to the unit test cases are correct, and free of human-error. ```cpp {caption="This is a caption" .Ruby} // multiple procedure with no duplicate names TEST_METHOD(checkTokens_noDupProcNames_returnsTrue) { std::string simpleCode = std::string("procedure x { a = 1; }") + std::string("procedure y { b = 2; }"); // Calls the tokeniser to generate the tokenised source for the semantic checker to check FrontEndSemanticChecker checker = FrontEndSemanticChecker(FrontEndTokenizer::tokenize(simpleCode)); bool isSemanticCorrect = checker.check(); Assert::IsTrue(isSemanticCorrect); } ``` ##### Integration Testing Integration Testing is a level of software testing where individual units are combined and tested as a group. The purpose of this level of testing is to expose faults in the interaction between integrated units. Test drivers and test stubs are often used to assist in Integration Testing. Integration Testing can be done using Black Box Testing, White Box Testing or Gray Box Testing methods.White Box Integration Testing is used for this SPA application. Integration Testing is done by the developers who are in charged of the major components. They should have previously worked on components that required information from the other party. They will have a better understanding on the interactions of the different components as compared to the rest of the team. **FrontEndParser - Design Extractor** interactions, **Design Extractor - PKB** interactions and **QueryEvaluator - PKB** interactions are being tested during the integration testing. ```cpp // Integration Testing between FrontEndParser and Design Extractor TEST_METHOD(singleProc_withoutContainer) { std::string fileName = "../Tests/Sample_source_without_container.txt"; FileOpener f(fileName); FrontEndParser parser; parser.parse(f.getContents()); PKB* pkb = PKB::getInstance(); DesignExtractor designExtractor; designExtractor.extractDesigns(); // Check stmt entries Assert::AreEqual(6, pkb->getStmtTableSize()); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::ASSIGN), getEntityStr(pkb->getStmtType(1))); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::ASSIGN), getEntityStr(pkb->getStmtType(2))); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::ASSIGN), getEntityStr(pkb->getStmtType(3))); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::PRINT), getEntityStr(pkb->getStmtType(4))); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::READ), getEntityStr(pkb->getStmtType(5))); Assert::AreEqual(getEntityStr(PQLConstants::DesignEntity::PRINT), getEntityStr(pkb->getStmtType(6))); // Check var entries Assert::AreEqual(5, pkb->getVarTableSize()); Assert::AreEqual(0, pkb->getVarNameIndex("a")); Assert::AreEqual(1, pkb->getVarNameIndex("b")); Assert::AreEqual(2, pkb->getVarNameIndex("c")); Assert::AreEqual(3, pkb->getVarNameIndex("x")); Assert::AreEqual(4, pkb->getVarNameIndex("d")); // Check proc entries std::string expectedProc1 = "ExaMpLe"; Assert::AreEqual(1, pkb->getProcTableSize()); Assert::AreEqual(expectedProc1, pkb->getProcName(0)); // Check follows entries Assert::AreEqual(5, pkb->getFollowsTableSize()); Assert::IsTrue(pkb->isFollows(1, 2)); Assert::IsTrue(pkb->isFollows(2, 3)); Assert::IsTrue(pkb->isFollows(3, 4)); Assert::IsTrue(pkb->isFollows(4, 5)); Assert::IsTrue(pkb->isFollows(5, 6)); // Check followsStar entries Assert::AreEqual(5, pkb->getFollowsStarTableSize()); Assert::IsTrue(pkb->isFollowsStar(1, 2)); Assert::IsTrue(pkb->isFollowsStar(1, 3)); Assert::IsTrue(pkb->isFollowsStar(1, 4)); Assert::IsTrue(pkb->isFollowsStar(1, 5)); Assert::IsTrue(pkb->isFollowsStar(1, 6)); Assert::IsTrue(pkb->isFollowsStar(2, 3)); Assert::IsTrue(pkb->isFollowsStar(2, 4)); Assert::IsTrue(pkb->isFollowsStar(2, 5)); Assert::IsTrue(pkb->isFollowsStar(2, 6)); Assert::IsTrue(pkb->isFollowsStar(3, 4)); Assert::IsTrue(pkb->isFollowsStar(3, 5)); Assert::IsTrue(pkb->isFollowsStar(3, 6)); Assert::IsTrue(pkb->isFollowsStar(4, 5)); Assert::IsTrue(pkb->isFollowsStar(4, 6)); Assert::IsTrue(pkb->isFollowsStar(5, 6)); // Check parent entries Assert::AreEqual(0, pkb->getParentTableSize()); // Check parentStar entries Assert::AreEqual(0, pkb->getParentStarTableSize()); // Check uses entries Assert::AreEqual(4, pkb->getUsesTableSize()); Assert::IsTrue(pkb->isUses(2, pkb->getVarNameIndex("a"))); Assert::IsTrue(pkb->isUses(3, pkb->getVarNameIndex("a"))); Assert::IsTrue(pkb->isUses(3, pkb->getVarNameIndex("b"))); Assert::IsTrue(pkb->isUses(4, pkb->getVarNameIndex("a"))); Assert::IsTrue(pkb->isUses(6, pkb->getVarNameIndex("d"))); // Check modifies entries Assert::AreEqual(4, pkb->getModifiesTableSize()); Assert::IsTrue(pkb->isModifies(1, pkb->getVarNameIndex("a"))); Assert::IsTrue(pkb->isModifies(2, pkb->getVarNameIndex("b"))); Assert::IsTrue(pkb->isModifies(3, pkb->getVarNameIndex("c"))); Assert::IsTrue(pkb->isModifies(5, pkb->getVarNameIndex("x"))); } ``` ##### System Testing System Testing is a level of testing that validates the complete and fully integrated software product. System Testing is a form of Black Box Testing, where the Application Under Test (AUT) is tested without looking at the internal code structure. The purpose of a system test is to evaluate the end-to-end system requirements and specifications. ![](https://i.imgur.com/idyaeoS.png) ![](https://i.imgur.com/MSoOhFb.png) System Testing is done by the developer who was not involved in developing majority of the SPA components. The tester will follow the requirements of the SPA and generate SIMPLE source program which are: 1. Valid SIMPLE source program 1.1 No nesting program 1.2 One layer nesting program 1.3 Multi layer nesting program 2. Invalid SIMPLE source program 2.1 Syntactically correct but semantically incorrect 2.2 Semantically correct but syntactically incorrect ``` // SIMPLE Program with One Nesting Layer procedure riVia { read geralt; if (geralt <= 3 * ciri) then { if (a <= c) then { print d; } else { print d; } while (ciri != d / 1) { f = e - 2; } } else { ciri = 4; } ciri = 5 / d; while (geralt == a) { read b; while (a > b + 1) { geralt = geralt - 3; print geralt; read yen; } if ((yen < 1) && (geralt > 0)) then { yen = yen + 2; geralt = 1; } else { yen = yen * geralt + 1; a = 23 - b / a; print yen; } } a = c; } ``` The tester will also generate PQL queries which are: 1. Valid PQL Queries 2. Invalid PQL Queries 2.1 Syntactically correct and grammatically correct, but semantically incorrect 2.2 Grammatically correct and semantically correct but syntactically incorrect 2.3 Semantically correct and syntactically correct but grammatically incorrect ``` // Valid PQL Query read r; Select r // Semantically incorrect PQL Query assign a; Select a such that Follows(a,a) // Syntactically incorrect PQL Query assign a Select a // Grammatically incorrect PQL Query assign a; Select a such that Follows(a,"a") ``` The rationale behind choosing a developer who is least involved in the SPA development is to ensure that the system test can be done without the knowledge of the internal code as much as possible. #### Test Schedule Given a 6-week time schedule, the following test schedule ensures that any unforseen circumstances and logical bugs can be rectify in time, and keeps the team on track to meet their deadline for Iteration 1. | Week | Tasks | Remarks | | ---- | ---------------------------------- | ------- | | 0 | Planning of test cases | - | | 1 | SPA development & Unit Testing | - | | 2 | Unit Testing & Integration Testing | Continue development & bug fixes | | 3 | Integration Testing & System Testing | Continue development & bug fixes | | 4 | Buffer period for bug fixes | - | #### Tools To report and keep track of bugs found, the team uses Github Issues. From those Github Issues, developers then take up those bug issues and resolve them. A batch script is also used to automate the System Testing so multiple SIMPLE source programs can be evaluated against their corresponding PQL queries. #### Features to be Tested In SPA iteration 1, we will be testing the following features: 1. Frontend SPA Parser 1.1 Frontend SPA Tokeniser 1.2 Frontend SPA Syntax Checker 1.3 Frontend SPA Semantic Checker 2. PQL Parser 2.1 PQL Tokeniser 2.2 PQL Syntax Checker 2.3 PQL Semantic Checker 3. PKB 4. Design Processor 5. Results Table 6. Synonym Table 7. Expression Utility 8. Evaluator Utility #### Features not Tested In SPA iteration 1, we only focus on the requirements listed in the [Basic SPA Requirement document](https://wiki.nus.edu.sg/display/CAS2/Basic+SPA+requirements). These are are some of the features we have yet to test in iteration 1 and will cover by the end of iteration 2: 1. Parsing of SIMPLE Program with more than 1 procedure 2. Parsing and evaluating queries with multiple clauses 3. Extracting remaining relationships listed in the [Full SPA Requirement document](https://wiki.nus.edu.sg/pages/viewpage.action?pageId=283480193) ( E.g. Next, Calls, Affects, etc.) ### Examples of Test Cases **PQLProcessor Unit Tests** #1 Unit test for PQLTokenizer Rationale: Ensure basic tokenizing function works correctly. Expected result: String successfully split into vector of tokens. ```cpp TEST_METHOD(tokenize_basicQuery_returnTokenized) { std::vector<std::string> expectedTokens; std::vector<std::string> actualTokens; std::string basicQuery = "stmt st; Select st"; expectedTokens.emplace_back("stmt"); expectedTokens.emplace_back("st"); expectedTokens.emplace_back(";"); expectedTokens.emplace_back("Select"); expectedTokens.emplace_back("st"); actualTokens = PQLTokenizer::tokenize(basicQuery); Assert::AreEqual(expectedTokens.size(), actualTokens.size()); for (size_t i = 0; i < expectedTokens.size(); i++) { Assert::AreEqual(expectedTokens.at(i), actualTokens.at(i)); } } ``` #2 Unit test case for ResultsTable Rationale: Ensure table intersects results correctly when existing index is inserted. Expected result: Only intersected values to remain in table. ```cpp TEST_METHOD(insert_singleValueSameIndex_returnsIntersection) { int index = 0; std::unordered_set<int> values1 = { 2,3,4,5,6 }; std::unordered_set<int> values2 = { 6,7,8,9 }; ResultsTable resultTable; resultTable.insert(index, values1); resultTable.insert(index, values2); std::vector<int> expected = { 6 }; std::vector<int> returnValue = resultTable.get(index); std::sort(returnValue.begin(), returnValue.end()); Assert::IsTrue(returnValue == expected); } ``` **System Tests** #1 Test query with no constraint Rationale: Ensure that the system can select all print statements properly in the absence of clauses. Input: Source code with the listed statement numbers being print statements Expected result: All print statements returned. ```cpp 3 - no constraint: print print pn; Select pn 10,14,35,44,49,50,58,60,61 5000 ``` #2 Test query with one such that clause and one pattern Rationale: Ensure that the system can select print statements which satisfy the given Follows* relationship and pattern. Input: Source code with no statements satisfying the query. Expected result: No statement returned. ```cpp 193 - pattern + Follows*: print print pn; assign a; stmt s; Select pn such that Follows*(pn, a) pattern a(_, "a") none 5000 ``` ## Discussion The following issues will be addressed as we embarked on this project: What worked fine for you? What was a problem? We found that we managed to split up the work as best-fit as possible, which was ideal as this made our working experience within the group a very positive one. Communication was key in the projects, and we found the weekly face-to-face meetings before consultation bridged any gaps that we may have for each other. We felt that it was easier to make group decisions during the meetings, compared to making it online. These factors contributed to the minimal miscommunication issues we faced when working on the project. A problem that we faced was not ensuring everyone was fully kept up-to-date on components that one was not responsible for. While this wasn't much an issue, we felt that our group meetings could have been more efficient as time taken to explain implementation problems could have been saved. Thankfully, all of us were clear on the specifications of each component, so the quality of our discussions were still preserved. What would you do differently if you were to start the project again? Following up on the problem surfaced on the previous question, we think that individually, we could have announced specific implementaion designs and data structures used for components that we are responsible for. We think that this can allow others to catch any loopholes in the general implementation idea, as more heads are better than one or two. While in practice, this may be hard to do, exercising discipline to perform this task will be required. We feel that this will be very beneficial given that all of us are new to this project, such that we can be able to maximise our learning. What management lessons have you learned? Time management was something we already learnt, but applied in great detail during this project. Given the tight schedule and commitments in other modules and school activities, we think that the enforcement of our set deadlines, albeit with some exceptions and adjustments, had taught us how important it is to manage our time. We did not have to put hasty last-minute effort because we were lax in our time management. Managing components' coordination between one another was also something we learnt. Apart from the overall coordination that one of us had to manage, the individual efforts to ensure one's component is well coordinated with a relevant one was important as well. For example, integration between PKB and FrontEnd will be managed by the developers assigned to the relevant components. ## Documentation of PKB Abstract APIs ### Variable API **Overview**: Stores variable information from the Parser. **API:** **VOID** insertVarTable(**VARNAME** varName); **Description:** Inserts the input variable name. **VARNAME** getVarName(**VARINDEX** varNameIndex); **Precondition:** The input variable index is valid. **Description:** Returns the variable name of the corresponding input variable index. **VARINDEX** getVarNameIndex(**VARNAME** varName); **Description:** If the input variable name is valid, return its corresponding variable index. Otherwise, returns -1 (special value) **LIST\<VARINDEX\>** getAllVarNameIndex(); **Description:** Returns a list of variable name indices. If there are no variables, returns an empty list. **SIZE** getVarTableSize(); **Description:** Returns the total number of variable names. ### Constants API **Overview**: Stores information on constants from the Parser. **API:** **VOID** insertConstantTable(**STMTNUM** stmtNum, **CONSTANT** constant); **Description:** Inserts the input statement number and its corresponding input constant. **LIST\<CONSTANT\>** getAllConstantsFromStmtNum(**STMTNUM** stmtNum); **Description:** Returns a list of all constants of the corresponding input statement number. If the input statement number is invalid, returns an empty list. **LIST\<STMTNUM\>** getAllStmtNumsFromConstant(**CONSTANT** constant); **Description:** Returns a list of all statement numbers of the corresponding input constant. If the input constant is invalid, returns an empty list. **LIST\<CONSTANT\>** getAllConstants(); **Description:** Returns a list of all constants. If there are no constants, returns an empty list. **SIZE** getConstantTableMapSize(); **Description:** Returns the total number of constants. ### Procedure API **Overview:** Stores procedure information from the Parser. **API:** **VOID** insertProcName(**PROCNAME** procName); **Description:** Inserts the input procedure name. **PROCNAME** getProcName(**PROCINDEX** procNameIndex); **Precondition**: The input procedure index is valid. **Description:** Returns the procedure name of the corresponding input procedure index. **PROCINDEX** getProcNameIndex(**PROCNAME** procName); **Description:** If the input procedure name is valid, returns its corresponding procedure index. Otherwise, returns -1 (special value) **LIST\<PROCINDEX\>** getAllProcNameIndex(); **Description:** Returns a list of procedure indices. If there are no procedures, returns an empty list. **SIZE** getProcTableSize(); **Description:** Returns the total number of procedures. ### Procedure and Statement API **Overview:** Stores procedure information and its corresponding statement numbers. **API:** **VOID** insertProcStmtTable(**PROCNAME** procName, **STMTNUM** stmtNum); **Precondition:** The input procedure name is valid. **Description:** Inserts the input procedure name and its corresponding input statement number. **LIST\<STMTNUM\>** getAllStmtNumsFromProcNameIndex(**PROCINDEX** procNameIndex); **Description:** Returns a list of all statement numbers of the corresponding input procedure index. If the input procedure index is invalid, returns an empty list. **PROCINDEX** getProcNameIndexFromStmtNum(**STMTNUM** stmtNum); **Description:** If input statement number is valid, returns its corresponding procedure index. Otherwise, returns -1 (special value) ### Statement API **Overview:** Stores statement number and its corresponding statement type. **API:** **VOID** insertStmtTable(**STMTNUM** stmtNum, **STMTTYPE** stmtType); **Description:** Inserts the input statement number and its corresponding statement type. **STMTTYPE** getStmtType(**STMTNUM** stmtNum); **Description:** If input statement number is valid, returns the corresponding statement type of the input statement number. Otherwise, returns INVALID (special value). **LIST\<STMTNUM\>** getAllStmtNumsFromStmtType(**STMTTYPE** stmtType); **Description:** Returns a list of all statement numbers of the corresponding input statement type. If there are no statement numbers with the input statement type, returns an empty list. **SIZE** getStmtTableSize(); **Description:** Returns the total number of statement numbers in the stmtTable. ### Parent API **Overview:** Stores Parent design abstraction relationship from the Parser. **API:** **VOID** insertParentTable(**STMTNUM** parentStmtNum, **STMTNUM** childStmtNum); **Precondition:** This method is only called if Parent(parentStmtNum, childStmtNum) design abstraction relationship is true. **Description:** Inserts the Parent design abstraction relationship with the input parent statement number and its corresponding input child statement number. **LIST\<STMTNUM\>** getChildren(**STMTNUM** parentStmtNum); **Description:** Returns a list of all child statement numbers of Parent design abstraction relationship with the corresponding input parent statement number. If there are no Parent design abstraction relationship with the input parentStmtNum, returns an empty list. **LIST\<STMTNUM\>** getAllChildren(); **Description:** Returns a list of all child statement numbers of Parent design abstraction relationship. If there are no Parent design abstraction relationship, returns an empty list. **LIST\<STMTNUM\>** getParent(**STMTNUM** childStmtNum); **Description:** Returns a list of all parent statement numbers of Parent design abstraction relationship with the corresponding input child statement number. If there are no Parent design abstraction relationship with the input child statement number, returns an empty list. **LIST\<STMTNUM\>** getAllParent(); **Description:** Returns a list of all parent statement numbers of Parent design abstraction relationship. If there are no Parent design abstraction relationship, returns an empty list. **BOOLEAN** isParent(**STMTNUM** parentStmtNum, **STMTNUM** childStmtNum); **Description:** Returns true if the Parent(parentStmtNum, childStmtNum) design abstraction relationship is true. Otherwise, returns false. **BOOLEAN** hasChildren(**STMTNUM** parentStmtNum); **Description:** Returns true if there is at least one Parent design abstraction relationship with the input parent statement number. Otherwise return false. **BOOLEAN** hasParent(**STMTNUM** childStmtNum); **Description:** Returns true if there is at least one Parent design abstraction relationship with the input child statement number. Otherwise return false. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getParentPairsByParentStmtNum(**STMTNUM** parentStmtNum); **Description:** Returns a list of all the Parent design abstraction relationship pairs which contains the corresponding input parent statement number. If there are no Parent design abstraction relationship with the input parent statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getParentPairsByChildStmtNum(**STMTNUM** childStmtNum); **Description:** Returns a list of all the Parent design abstraction relationship pairs which contains the corresponding input child statement number. If there are no Parent design abstraction relationship with the input child statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getAllParentPairs(); **Description:** Returns a list of all the Parent design abstraction relationship pairs. If there are no Parent design abstraction relationship, returns an empty list. ### Parent* API **Overview:** Stores Parent* design abstraction relationship from the Parser/design extractor. **API:** **VOID** insertParentStarTable(**STMTNUM** parentStarStmtNum, **STMTNUM** childStmtNum); **Precondition:** This method is only called if Parent*(parentStarStmtNum, childStmtNum) design abstraction relationship is true. **Description:** Inserts the Parent* design abstraction relationship with the input parent star statement number and its corresponding input child statement number. **LIST\<STMTNUM\>** getChildrenStar(**STMTNUM** parentStarStmtNum); **Description:** Returns a list of all child statement numbers of Parent* design abstraction relationship with the corresponding input parent star statement number. If there are no Parent* design abstraction relationship with the input parent star statement number, returns an empty list. **LIST\<STMTNUM\>** getAllChildrenStar(); **Description:** Returns a list of all child statement numbers of Parent* design abstraction relationship. If there are no Parent* design abstraction relationship, returns an empty list. **LIST\<STMTNUM\>** getParentStar(**STMTNUM** childStmtNum); **Description:** Returns a list of all parent star statement numbers of the Parent* design abstraction relationship with the corresponding input child statement number. If there are no Parent* design abstraction relationship with the input child statement number, returns an empty list. **LIST\<STMTNUM\>** getAllParentStar(); **Description:** Returns a list of all parent star statement numbers of Parent* design abstraction relationship. If there are no Parent* design abstraction relationship, returns an empty list. **BOOLEAN** isParentStar(**STMTNUM** parentStarStmtNum, **STMTNUM** childStmtNum); **Description:** Returns true if the Parent(parentStarStmtNum, childStmtNum) design abstraction relationship is true. Otherwise, returns false **BOOLEAN** hasChildrenStar(**STMTNUM** parentStarStmtNum); **Description:** Returns true if there is at least one Parent* design abstraction relationship with the input parent star statement number. Otherwise, returns false. **BOOLEAN** hasParentStar(**STMTNUM** childStmtNum); **Description:** Returns true if there is at least one Parent* design abstraction relationship with the input child statement number. Otherwise, returns false. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getParentStarPairsByParentStarStmtNum(**STMTNUM** parentStarStmtNum); **Description:** Returns a list of all the Parent* design abstraction relationship pairs which contains the corresponding input parent star statement number. If there are no Parent* design abstraction relationship with the input parent star statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getParentStarPairsByChildStmtNum(**STMTNUM** childStmtNum); **Description:** Returns a list of all the Parent* design abstraction relationship pairs which contains the corresponding input childStmtNum. If there are no Parent* design abstraction relationship with the input child statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getAllParentStarPairs(); **Description:** Returns a list of all the Parent* design abstraction relationship pairs. If there are no Parent* design abstraction relationship, returns an empty list. ### Follows API **Overview:** Stores Follows design abstraction relationship from the Parser. **API:** **VOID** insertFollowsTable(**STMTNUM** leftStmtNum, **STMTNUM** rightStmtNum); **Precondition:** This method is only called if Follows(leftStmtNum, rightStmtNum) design abstraction relationship is true. **Description:** Inserts the Follows design abstraction relationship with the input left statement number and its corresponding right statement number. **STMTNUM** getFollows(**STMTNUM** leftStmtNum); **Description:** Returns the corresponding right statement number of the Follows design abstraction relationship with the input left statement number. If there are no Follows design abstraction relationship with the input left statement number, returns -1 (special value). **STMTNUM** getFollowsBy(**STMTNUM** rightStmtNum); **Description:** Returns the corresponding left statement number of Follows design abstraction relationship with the input right statement number. If there are no Follows design abstraction relationship with the input right statement number, returns -1 (special value). **BOOLEAN** isFollows(**STMTNUM** leftStmtNum, **STMTNUM** rightStmtNum); **Description:** Returns true if the Follows(leftStmtNum, rightStmtNum) design abstraction relationship is true. Otherwise, returns false. **BOOLEAN** hasFollows(**STMTNUM** leftStmtNum); **Description:** Returns true if there is a Follows design abstraction relationship with the input left statement number. Otherwise, returns false. **BOOLEAN** hasFollowsBy(**STMTNUM** rightStmtNum); **Description:** Returns true if there is a Follows design abstraction relationship with the input right statement number. Otherwise, returns false. **LIST\<STMTNUM\>** getAllFollows(); **Description:** Returns a list of all right statement numbers of Follows design abstraction relationship. If there are no Follows design abstraction relationship, returns an empty list. **LIST\<STMTNUM\>** getAllFollowsBy(); **Description:** Returns a list of all left statement numbers of Follows design abstraction relationship. If there are no Follows design abstraction relationship, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getAllFollowsPairs(); **Description:** Returns a list of all the Follows design abstraction relationship pairs. If there are no Follows design abstraction relationship, returns an empty list. ### Follows* API **Overview:** Stores Follows* design abstraction relationship from the Parser/design extractor. **API:** **VOID** insertFollowsStarTable(**STMTNUM** leftStmtNum, **STMTNUM** rightStmtNum); **Precondition:** This method is only called if Follows*(leftStmtNum, rightStmtNum) design abstraction relationship is true. **Description:** Inserts the Follows* design abstraction relationship with the input left statement number and its corresponding right statement number. **LIST\<STMTNUM\>** getFollowsStar(**STMTNUM** leftStmtNum); **Description:** Returns a list of all right statement numbers of the Follows* design abstraction relationship with the corresponding input left statement number. If there are no Follows* design abstraction relationship with the input left statement number, returns an empty list. **LIST\<STMTNUM\>** getFollowsStarBy(**STMTNUM** rightStmtNum); **Description:** Returns a list of all left statement numbers of the Follows* design abstraction relationship with the corresponding input right statement number. If there are no Follows* design abstraction relationship with the input right statement number, returns an empty list. **BOOLEAN** isFollowsStar(**STMTNUM** leftStmtNum, **STMTNUM** rightStmtNum); **Description:** Returns true if the Follows*(leftStmtNum, rightStmtNum) design abstraction relationship is true. Otherwise, returns false. **BOOLEAN** hasFollowsStar(**STMTNUM** leftStmtNum); **Description:** Returns true if there is at least one Follows* design abstraction relationship with the input left statement number. Otherwise, returns false. **BOOLEAN** hasFollowsStarBy(**STMTNUM** rightStmtNum); **Description:** Returns true if there is at least one Follows* design abstraction relationship with the input right statement number. Otherwise, returns false. **LIST\<STMTNUM\>** getAllFollowsStar(); **Description:** Returns a list of all right statement numbers of Follows* design abstraction relationship. If there are no Follows* design abstraction relationship, returns an empty list. **LIST\<STMTNUM\>** getAllFollowsStarBy(); **Description:** Returns a list of all left statement numbers of Follows* design abstraction relationship. If there are no Follows* design abstraction relationship, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getFollowsStarPairsByLeftStmtNum(**STMTNUM** leftStmtNum); **Description:** Returns a list of all the Follows* design abstraction relationship pairs which contains the corresponding input left statement number. If there are no Follows* design abstraction relationship with the input left statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getFollowsStarPairsByRightStmtNum(**STMTNUM** rightStmtNum); **Description:** Returns a list of all the Follows* design abstraction relationship pairs which contains the corresponding input right statement number. If there are no Follows* design abstraction relationship with the input right statement number, returns an empty list. **LIST\<PAIR\<STMTNUM, STMTNUM\>\>** getAllFollowsStarPairs(); **Description:** Returns a list of all the Follows* design abstraction relationship pairs. If there are no Follows* design abstraction relationship, returns an empty list. ### Modifies API **Overview:** Stores Modifies design abstraction relationship involving statement numbers and variables from the Parser/design extractor. **API:** **VOID** insertModifiesTable(**STMTNUM** stmtNum, **VARNAME** varName); **Precondition:** This method is only called if Modifies(stmtNum, varName) design abstraction relationship is true. **Description:** Inserts the Modifies design abstraction relationship with the input statement number and its corresponding input variable name. **VOID** insertModifiesTableByIndex(**STMTNUM** stmtNum, **VARINDEX** varNameIndex); **Precondition:** This method is only called if Modifies(stmtNum, varName) design abstraction relationship is true. **Description:** Inserts the Modifies design abstraction relationship with the input statement number and its corresponding variable name from its input variable index. **BOOLEAN** isModifies(**STMTNUM** stmtNum, **VARINDEX** varNameIndex); **Description:** Returns true if the Modifies(stmtNum, varName) design abstraction relationship is true where variable name is from the input variable index. Otherwise, returns false. **BOOLEAN** hasModifies(**STMTNUM** stmtNum); **Description:** Returns true if there is at least one Modifies design abstraction relationship with the input statement number. Otherwise, returns false. **LIST\<VARINDEX\>** getModifies(**STMTNUM** stmtNum); **Description:** Returns a list of all variable index of the Modifies design abstraction relationship with the input statement number. If there are no Modifies design abstraction relationship with the input statement number, returns an empty list. **BOOLEAN** hasModified(**VARINDEX** varNameIndex); **Description:** Returns true if there is at least one Modifies design abstraction relationship involving statement numbers and variables with the variable name from the input variable index. Otherwise, returns false. **LIST\<STMTNUM\>** getModified(**VARINDEX** varNameIndex); **Description:** Returns a list of all statement numbers of Modifies design abstraction relationship involving statement numbers and variables with the variable name from the input variable index. If there are no Modifies design abstraction relationship involving statement numbers and variables with the variable name from the input variable index, returns an empty list. **LIST\<STMTNUM\>** getAllModified(); **Description:** Returns a list of all statement numbers with Modifies design abstraction relationship. If there are no Modifies design abstraction relationship involving statement numbers and variables, returns an empty list. **LIST\<PAIR\<STMTNUM, VARINDEX\>\>** getAllModifiesPairs(); **Description:** Returns a list of all the Modifies design abstraction relationship pairs involving statement number and variables. If there are no Modifies design abstraction relationship involving statement numbers and variables, returns an empty list. ### Modifies and Procedure API **Overview:** Stores Modifies design abstraction relationship involving procedures and variables from the Parser/design extractor. **API:** **VOID** insertModifiesProcTable(**PROCNAME** procName, **VARNAME** varName); **Precondition:** This method is only called if Modifies(procName, varName) design abstraction relationship is true. **Description:** Inserts the Modifies design abstraction relationship with the input procedure name and its corresponding input variable name. **VOID** insertModifiesProcTableByIndex(**PROCINDEX** procNameIndex, **VARINDEX** varNameIndex); **Precondition:** This method is only called if Modifies(procName, varName) design abstraction relationship is true. **Description:** Inserts the Modifies design abstraction relationship with the procedure name from the input procedure index and its corresponding variable name from the input variable index. **BOOLEAN** isModifiesProc(**PROCINDEX** procNameIndex, **VARINDEX** varNameIndex); **Description:** Returns true if Modifies(procName, varName) design abstraction relationship is true where the procedure name and variable name are from their respective input index. Otherwise, returns false. **BOOLEAN** hasModifiesProc(**PROCINDEX** procNameIndex); **Description:** Returns true if there is at least one Modifies design abstraction relationship with the procedure name from the input procedure index. Otherwise, returns false. **LIST\<VARINDEX\>** getModifiesProc(**PROCINDEX** procNameIndex); **Description:** Returns a list of all variable index of Modifies design abstraction relationship with the procedure name from the input procedure index. If there are no Modifies design abstraction relationship with the procedure name from the input procedure index, returns an empty list. **BOOLEAN** hasModifiedProc(**VARINDEX** varNameIndex); **Description:** Returns true if there is at least one Modifies design abstraction relationship involving procedures and variables with the variable name from the input variable index. Otherwise, returns false. **LIST\<PROCINDEX\>** getModifiedProc(**VARINDEX** varNameIndex); **Description:** Returns a list of all procedure index of Modifies design abstraction relationship with the variable name from the input variable index. If there are no Modifies abstraction relationship involving procedures and variables with the variable name from the input variable index, returns an empty list. **LIST\<PROCINDEX\>** getAllModifiedProc(); **Description:** Returns a list of all procedure index with Modifies design abstraction relationship. If there are no Modifies design abstraction relationship involving procedures and variables, returns an empty list. **LIST\<PAIR\<PROCINDEX, VARINDEX\>\>** getAllModifiesProcPairs(); **Description:** Returns a list of all the Modifies design abstraction relationship involving procedures and variables. If there are no Modifies design abstraction relationship involving procedures and variables, returns an empty list. ### Uses API **Overview:** Stores Uses design abstraction relationship involving statement numbers and variables from the Parser/design extractor. **API:** **VOID** insertUsesTable(**STMTNUM** stmtNum, **VARNAME** varName); **Precondition:** This method is only called if Uses(stmtNum, varName) design abstraction relationship is true. **Description:** Inserts the Uses design abstraction relationship with the input statement number and its corresponding input variable name. **VOID** insertUsesTableByIndex(**STMTNUM** stmtNum, **VARINDEX** varNameIndex); **Precondition:** This method is only called if Uses(stmtNum, varName) design abstraction relationship is true. **Description:** Inserts the Uses design abstraction relationship with the input statement number and its corresponding variable name from its input variable index. **BOOLEAN** isUses(**STMTNUM** stmtNum, **VARINDEX** varNameIndex); **Description:** Returns true if Uses(stmtNum, varName) design abstraction relationship is true where variable name is from the input variable index. Otherwise, returns false. **BOOLEAN** hasUses(**STMTNUM** stmtNum); **Description:** Returns true if there is at least one Uses design abstraction relationship with the input statement number. Otherwise, returns false. **LIST\<VARINDEX\>** getUses(**STMTNUM** stmtNum); **Description:** Returns a list of all variable index of the Uses design abstraction relationship with the input statement number. If there are no Uses design abstraction relationship with the input statement number, returns an empty list. **BOOLEAN** hasUsed(**VARINDEX** varNameIndex); **Description:** Returns true if there is at least one Uses design abstraction relationship involving statement numbers and variables with the variable name from the input variable index. Otherwise, returns false. **LIST\<STMTNUM\>** getUsed(**VARINDEX** varNameIndex); **Description:** Returns a list of all statement numbers of Uses design abstraction relationship involving statement numbers and variable with the variable name from the input variable index. If there are no Uses design abstraction relationship involving statement numbers and variables with the variable name from the input variable index, returns an empty list. **LIST\<STMTNUM\>** getAllUsed(); **Description:** Returns a list of all statements numbers with Uses design abstraction relationship. If there are no Uses design abstraction relationship involving statement numbers and variables, returns an empty list. **LIST\<PAIR\<STMTNUM, VARINDEX\>\>** getAllUsesPairs(); **Description:** Returns a list of all the Uses design abstraction relationship pairs involving statement numbers and variables. If there are no Uses design abstraction relationship involving statement numbers and variables, returns an empty list. ### Uses and Procedure API **Overview:** Stores Uses design abstraction relationship involving procedures and variables from the Parser/design extractor. **API:** **VOID** insertUsesProcTable(**PROCNAME** procName, **VARNAME** varName); **Precondition:** This method is only called if Uses(procName, varName) design abstraction relationship is true. **Description:** Inserts the Uses design abstraction relationship with the input procedure name and its corresponding variable name. **VOID** insertUsesProcTableByIndex(**PROCINDEX** procNameIndex, **VARINDEX** varNameIndex); **Precondition:** This method is only called if Uses(procName, varName) design abstraction relationship is true. **Description:** Inserts the Uses design abstraction relationship with the procedure name from the input procedure index and its corresponding variable name from the input variable index. **BOOLEAN** isUsesProc(**PROCINDEX** procNameIndex, **VARINDEX** varNameIndex); **Description:** Returns true if Uses(procName, varName) design abstraction relationship is true where the procedure name and variable name are from their respective input index. Otherwise, returns false. **BOOLEAN** hasUsesProc(**PROCINDEX** procNameIndex); **Description:** Returns true if there is at least one Uses design abstraction relationship with the procedure name from the input procedure index. Otherwise, returns false. **LIST\<VARINDEX\>** getUsesProc(**PROCINDEX** procNameIndex); **Description:** Returns a list of all variable index of Uses design abstraction relationship with the procedure name from the input procedure index. If there are no Uses design abstraction relationship with the procedure name from the input procedure index, returns an empty list. **BOOLEAN** hasUsedProc(**VARINDEX** varNameIndex); **Description:** Returns true if there is at least one Uses design abstraction relationship with the variable name from the input variable index. Otherwise, returns false. **LIST\<PROCINDEX\>** getUsedProc(**VARINDEX** varNameIndex); **Description:** Returns a list of all procedure index of Uses design abstraction relationship with the variable name from the input variable index. If there are no Uses design abstraction relationship involving procedures and variables with the variable name from the input variable index, returns an empty list. **LIST\<PROCINDEX\>** getAllUsedProc(); **Description:** Returns a list of all procedure index with Uses design abstraction relationship. If there are no Uses design abstraction relationship involving procedures and variables, returns an empty list. **LIST\<PAIR\<PROCINDEX, VARINDEX\>\>** getAllUsesProcPairs(); **Description:** Returns a list of all the Uses design abstraction relationship involving procedures and variables. If there are no Uses design abstraction relationship involving procedures and variables, returns an empty list. ### Assignment expression API **Overview:** Stores full and partial assignment expression of assignment statements from the Parser/design extractor. **API:** **VOID** insertFullAssignExprTable(**STMTNUM** stmtNum, **ASSIGNEXPR** fullAssignExpr); **Precondition:** The input statement number and input full assignment expression are valid and are from assignment statements. **Description:** Inserts the assignment statement number and its corresponding full assignment expression from assignment statement. **LIST\<STMTNUM\>** getAllAssignStmtFromFullExpr(**ASSIGNEXPR** fullAssignExpr); **Description:** Returns a list of all assignment statement numbers with the corresponding input full assignment expression. **VOID** insertPartialAssignExprTable(**STMTNUM** stmtNum, **ASSIGNEXPR** partialAssignExpr); **Precondition:** The input statement number and input partial assignment expression are valid and are from assignment statements. **Description:** Inserts the assignment statement number and its corresponding partial assignment expression from assignment statement. **LIST\<STMTNUM\>** getAllAssignStmtFromPartialExpr(**ASSIGNEXPR** partialAssignExpr); **Description:** Returns a list of all assignment statement numbers with the corresponding input partial assignment expression. ### Miscellanous API **Overview:** Additional API methods that PKB has either to facilitate its operation or for testing purposes. **API:** **VOID** erasePKB(); **Description:** Clears all data structures such as varTable, procTable, etc so as to have a clean PKB (It is useful for testing purposes) **static PKB** getInstance(); **Description:** If PKB has already been initialised, returns the object instance of the PKB else, initialise a PKB instance. (For singleton pattern)