# UML diagram docs PQL Preprocessor ```plantuml @startuml participant PQL as pql participant PQLPreprocessor as preproc participant PQLLexer as lexer participant PQLParser as parser create preproc pql -> preproc : PQLPreprocessor() activate preproc preproc --> pql deactivate preproc pql -> preproc : parseQuery(query, queryObject) activate preproc create lexer preproc -> lexer : PQLLexer() activate lexer lexer --> preproc deactivate lexer preproc -> lexer : tokenize(query) activate lexer lexer --> preproc : tokens deactivate lexer create parser preproc -> parser : PQLParser(tokens) activate parser parser --> preproc deactivate parser preproc -> parser : parse(queryObject) activate parser parser --> preproc deactivate parser preproc --> pql deactivate preproc ``` PQL Lexer ```plantuml @startuml participant PQLPreprocessor as preproc participant PQLLexer as lexer activate preproc preproc -> lexer : tokenize(query) activate lexer loop character by character till end of query alt character is a whitespace lexer -> lexer : derive type of token from buffer activate lexer alt string in buffer is "assign" lexer --> lexer : TokenType::ASSIGN else string in buffer is "variable" lexer --> lexer : TokenType::VARIABLE else string in buffer is "stmt" lexer --> lexer : TokenType::STMT else a lot of other cases note left: Not all types of tokens \nare displayed end lexer --> lexer : TokenType deactivate lexer lexer -> lexer : add new token object \nto list of tokens activate lexer lexer --> lexer deactivate lexer lexer -> lexer : empty the buffer activate lexer lexer --> lexer deactivate lexer else char is not a whitespace lexer -> lexer : add character to buffer activate lexer lexer --> lexer deactivate lexer end end lexer --> preproc: list of tokens deactivate lexer @enduml ``` PQLParser ```plantuml @startuml participant PQLParser as parser -> parser : parse(selectedResults, synonyms, relations, patterns, withs) activate parser parser -> parser : parseDeclarations(synonyms, synonymsMap) activate parser loop next token is present && \nnext token is not of type SELECT parser -> parser : parseDeclaration(synonyms, synonymsMap) activate parser deactivate parser end deactivate parser parser -> parser : parseSelected(selectedResults, synonymsMap) activate parser deactivate loop next token is present alt next token is of type SELECT parser -> parser : parseRelations(relations, synonymsMap) activate parser deactivate parser else next token is of type PATTERN parser -> parser : parsePattern(patterns, synonymsMap) activate parser deactivate parser else next token is of type WITH parser -> parser : parseWiths(withs, synonymsMap) activate parser deactivate parser else doesn't match any of the tokens above note over parser: throw exception if still has tokens end end deactivate parser @enduml ``` parseDeclaration ```plantuml @startuml start :consume() and derive synonym type from the consumed token; while (next token is ";") is (no) if (is first synonym name) then (yes) else (no) :consume(","); endif :consumeName() and set synonym name as the consumed token; :REQUIRE synonym is not declared; :add Synonym with the type and name to synonyms list and synonyms map; endwhile (yes) :REQUIRE has parsed at least one name; stop @enduml ``` parseSelected ```plantuml @startuml start if (next token is BOOLEAN and BOOLEAN synonym is not declared) :parse boolean result; elseif (next token is "<") :parse multiple results; repeat :parse single result; repeatwhile (next token is not ">") elseif (next token is a valid name) :parse single result; else (no) :invalid syntax; endif stop @enduml ``` ```plantuml @startuml start :REQUIRE synonym is declared; if (next token is ".") then (yes) :parse attribute reference type; else (no) endif :construct the query result with the synonym and attribute type; :REQUIRE attribute type is a valid attribute for the synonym; :add the query result into list of selectedResults; stop @enduml ``` parse Pattern ```plantuml @startuml start :parse pattern synonym name; :REQUIRE pattern synonym is declared and can be pattern synonym; :set pattern type; while (query still has token and current token is not ")") is (yes) :parse the current and next token to determine parameter type and value; if (param type is SYNONYM) then (yes) :REQUIRE synonym is declared; else (no) endif :add argument with the type and value to the list of this pattern's arguments; endwhile (no) :REQUIRE pattern has correct argument size and types based on pattern type; :add pattern to list of patterns; stop @enduml ``` parsing multiple Relations ```plantuml @startuml start repeat :parse relation; repeatWhile(next token is "and") is (yes) ->no; stop @enduml ``` parse Relation ```plantuml @startuml start repeat :derive the type of relation from token; :parse LHS argument of relation; :parse RHS argument of relation; :REQUIRE that based on the type of relation, LHS\nand RHS the relation is valid; :Add new Relation object to existing list of Relations; repeatWhile(next token is "and") is (yes) ->no; stop @enduml ``` parsing Relation parameter ```plantuml @startuml start :derive the type of relation parameter from token; if (relation parameter is a synonym) then (yes) :REQUIRE synonym has been declared in the query; else (no) endif if (relation parameter is a synonym or string) then (yes) :REQUIRE them to have a valid name; else (no) endif :return type of relation parameter; stop @enduml ``` parsing multiple Withs ```plantuml @startuml start repeat :parse with; repeatWhile(next token is "and") is (yes) ->no; stop @enduml ``` parse With ```plantuml @startuml start :parse LHS argument of with; :parse RHS argument of with; :REQUIRE that based on the type of with, LHS\nand RHS the with is valid; :Add new With object to existing list of Withs; stop @enduml ``` parsing With parameter ```plantuml @startuml start :derive the type of with parameter \nfrom the next two tokens; if (with parameter is a synonym \nor attribute reference) then (yes) :REQUIRE synonym has been \ndeclared in the query; note left: attribute reference is \na reference to a \nsynonym's attribute\n(therefore it also \nrequires synonym check) else (no) endif if (with parameter is a synonym) then (yes) :REQUIRE that the synonym can be \ninterpreted as a program line; else (no) endif if (with parameter is an attribute reference) then (yes) :derive the type of attribute being \nreferenced from the next token; else (no) endif if (with parameter is an attribute \nreference, synonym or string) then (yes) :REQUIRE them to have a valid name; else (no) endif :return type of with parameter; stop @enduml ``` PQL ```plantuml @startuml participant PQL as pql participant PQLPreprocessor as preproc participant PQLEvaluator as eval participant PKB as pkb --> pql : run(query) activate pql create preproc pql -> preproc: PQLPreprocessor() activate preproc pql <-- preproc deactivate preproc pql -> preproc: parseQuery(query, queryObject) activate preproc note right: fills in the queryObject pql <-- preproc: deactivate preproc create eval pql -> eval: PQLEvaluator(pkb, queryObject) activate eval eval --> pql deactivate eval pql -> pkb: setUpBeforeQuery() activate pkb pkb --> pql deactivate pkb pql -> eval: evalQuery() activate eval note over eval: queries PKB pql <-- eval: result deactivate eval <-- pql: result deactivate pql @enduml ``` PQLEvaluator ```plantuml @startuml participant PQLEvaluator as eval create eval -> eval : PQLEvaluator(pkb, selectedResults, synonyms, relations, patterns, withs) activate eval eval -> eval: generateSynonymToIdMap() activate eval eval --> eval: synonymMap deactivate eval <-- eval deactivate eval @enduml ``` PQLEvaluator ```plantuml @startuml participant PQLEvaluator as eval participant PQLOptimizer as optimizer participant QuerySolver as solver -> eval : evalQuery() activate eval eval -> eval : fillCandidates() note right: Calls pkb getAllIds method\nbased on the synonym type\nand fill in synonymMap create optimizer eval -> optimizer: PQLOptimizer(pkb, relations, patterns, withs); activate optimizer eval <-- optimizer deactivate optimizer eval -> optimizer : filterCandidates(synonymMap) eval -> eval : generateConnectedComponents() activate eval eval --> eval : connectedComponents deactivate eval eval -> eval : getComponentWithAndWithoutSelected(connectedComponents) activate eval eval --> eval : [componentWithSelectedIdx, componentsWithoutSelected] deactivate eval eval -> eval : extractCandidates() note right: extracting pkbIds of each synonyms as a vector activate eval eval --> eval : candidates deactivate eval loop for each component in componentsWithoutSelected opt component.size() != 1 eval -> eval: makeAdjacencyList(component) activate eval eval --> eval: groupEdge deactivate eval create solver eval -> solver: QuerySolver<true>(groupEdge, candidates) activate solver eval <-- solver deactivate solver eval -> solver: solve() activate solver eval <-- solver: isSolvable deactivate solver note over solver: if not solvable, \nthrow exception end end loop opt componentWithSelected.size() != 1 eval -> eval: makeAdjacencyList(componentWithSelected) activate eval eval --> eval: groupEdge deactivate eval create solver eval -> solver: QuerySolver<false>(selectedSynIdx, groupEdge, candidates) activate solver eval <-- solver deactivate solver eval -> solver: solve() activate solver eval <-- solver: selectedIds deactivate solver end eval -> eval: transform(selectedIds, \ngetSynStr(curId, selectedResults[0].attrType, pkb)\n) activate eval eval --> eval: resultStrings deactivate eval <-- eval : answers @enduml ``` PQLOptimizer ```plantuml @startuml participant PQLOptimizer as eval -> eval : filterCandidates(synonymMap) activate eval note over eval: if pkbIds of some synonym is empty after filter, throw exception loop for each relation in relations alt number of synonyms in relation == 0 eval -> eval: filterCandidatesForZeroSynonymRelation(relation) else number of synonyms in relation == 1 eval -> eval: filterCandidatesForOneSynonymRelation(relation) else number of synonyms in relation == 2 eval -> eval: filterCandidatesForTwoSynonymRelation(relation) end end loop loop for each pattern in patterns opt number of synonyms in pattern == 1 eval -> eval: filterCandidatesForOneSynonymPattern(pattern) end end loop loop for each with in withs alt number of synonyms + attribute references in withs == 0 eval -> eval: filterCandidatesForZeroSynonymWith(with) else number of synonyms + attribute references in withs == 1 eval -> eval: filterCandidatesForOneSynonymWith(with) else number of synonyms + attribute references in withs == 2 eval -> eval: filterCandidatesForTwoSynonymWith(with) end end loop deactivate eval <-- eval ``` parseAssignment ```plantuml @startuml start :consume("read"); :consume token of type NAME; :consume(";"); :add statement information to PKB; stop @enduml ``` SourceProc ```plantuml @startuml SourceProc->SourceProc:runParser() activate SourceProc loop have token in deque SourceProc->SourceProc:parseProcedure() activate SourceProc SourceProc->SourceProc:consume("procedure") SourceProc->SourceProc:consume(TokenType::NAME) activate SourceProc SourceProc-->SourceProc:procedureName deactivate SourceProc SourceProc->SourceProc:addNewProcedure(procedureName) SourceProc->SourceProc:consume("{") SourceProc->SourceProc:parseStatements() SourceProc->SourceProc:consume("}") deactivate SourceProc end deactivate SourceProc @enduml ``` parseStmt ```plantuml @startuml SourceProc->SourceProc:parseAssignment() activate SourceProc SourceProc->SourceProc:consume(TokenType::NAME) activate SourceProc SourceProc-->SourceProc:lhs deactivate SourceProc SourceProc->SourceProc:consume("=") SourceProc->SourceProc:consumeUntil(";") activate SourceProc SourceProc-->SourceProc:rhs deactivate SourceProc SourceProc->ExpressionParser:verifyBinaryExpression(rhs) SourceProc->SourceProc:addNewStmt(StmtType::ASSIGNMENT, modifies = lhs, uses = extractAllName(rhs), consts = extractAllConsts(rhs), rhs) deactivate SourceProc @enduml ``` fillCandidates ```plantuml @startuml participant PQLEvaluator as eval participant Synonym as synonym participant PKB as pkb eval -> eval: fillCandidates(synonyms) activate eval loop synonym in synonyms eval -> synonym: getPkbIds(pkb) activate synonym synonym -> pkb: getAllIds([=](PkbId id) { pkb->isWhile(id)) } activate pkb synonym <-- pkb: pkbIds deactivate pkb eval <-- synonym: pkbIds note over eval: the synonymsCandidates\nfor this synonym is updated deactivate synonym deactivate synonym end eval --> eval deactivate eval @enduml ``` filterCandidates ```plantuml @startuml participant PQLOptimizer as eval participant Relation as rel participant PKB as pkb eval -> eval: filterCandidatesFor\nOneSynonymRelation(relation) activate eval alt if LHS is synonym eval -> rel: getRhsPkbId() activate rel rel -> pkb: getId(rhsString) activate pkb pkb --> rel: pkbId deactivate pkb rel --> eval: rhsPkbId deactivate rel loop lhsCandidatePkbId of LHS synonym's candidates eval -> rel: isHolds(lhsCandidatePkbId, \nrhsPkbId, pkb) activate rel alt if relation type is MODIFIES rel -> pkb: Modifies(lhsCandidatePkbId,\n rhsPkbId) activate pkb pkb --> rel: true/false deactivate pkb else other relation types note over eval: other relation types are\n queried accordingly to PKB API end rel --> eval: true/false deactivate rel alt true note over eval: keep lhsCandidatePkbId\nin LHS synonym's pkbIds else false note over eval: filter out lhsCandidatePkbId\nfrom LHS synonym's pkbIds end end end eval --> eval deactivate eval @enduml ``` PQL Lexer ```plantuml @startuml participant PQLPreprocessor as preproc participant PQLLexer as lexer activate preproc preproc -> lexer : tokenize(query) activate lexer loop character by character till end of query alt character is a whitespace lexer -> lexer : derive type of token from buffer activate lexer alt string in buffer is "assign" lexer --> lexer : TokenType::ASSIGN else string in buffer is "variable" lexer --> lexer : TokenType::VARIABLE else string in buffer is "stmt" lexer --> lexer : TokenType::STMT else a lot of other cases note left: Not all types of tokens \nare displayed end lexer --> lexer : TokenType deactivate lexer lexer -> lexer : add new token object \nto list of tokens activate lexer lexer --> lexer deactivate lexer lexer -> lexer : empty the buffer activate lexer lexer --> lexer deactivate lexer else char is not a whitespace lexer -> lexer : add character to buffer activate lexer lexer --> lexer deactivate lexer end end lexer --> preproc: list of tokens deactivate lexer @enduml ``` Flow of Lexer ```plantuml @startuml start :Receive PQL query; :Standardize Spacing of query; repeat :Iterate char by char to get contiguous block of characters; :Derive the token type of the contiguous block of characters; :Add new token with token type and the token string\nto a deque of tokens; repeatwhile(still have contiguous character blocks to tokenize) is (yes) ->no; :return deque of tokens; stop @enduml ``` Flow of Parse ```plantuml @startuml start :receive tokens; :parse declarations and fill \nin synonyms list and map; :parse selected results and \nfill in selected results list; repeat if (next token is such that) then (yes) :parse relations and \nfill in relations list; elseif (next token is pattern) then (yes) :parse patterns and \nfill in patterns list; elseif (next token is with) then (yes) :parse with clauses \nand fill in withs list; else (no) :syntax error; stop endif repeatwhile(still have token) is (yes) ->no; stop @enduml ``` Flow of deciding token type ```plantuml @startuml start note left: Assume that x is a contiguous\nblock of characters if (x is a reserved keyword) then (yes) :return TokenType of\nreserved keyword; stop else (no) if (x is quoted) then (yes) :TokenType QUOTED; stop else (no) if (x is all digits) then (yes) :TokenType INTEGER; stop else (no) if (x is a valid name) then (yes) :TokenType NAME; stop else (no) :Throw an exception; stop @enduml ``` Flow of PQLEvaluator ```plantuml @startuml start :initialize data structures; :fill the candidates of each relevant synonym; :evaluate clauses that contain no synonyms; :evaluate clauses involving 1 unique synonym to filter candidates of the synonym; :generate synonym groupings; :generate adjacency list (clause constraint between synonyms as predicate) for each group; :separate group containing and not containing selected result; :solve each groups not containing selected result involving more than 1 unique synonym; :REQUIRE those groups have at least one satisfying candidates tuple; :solve each groups containing selected result involving more than 1 unique synonym; :perform cross product to generate raw result table; :convert the result table to their design entity or attribute values; stop @enduml ``` ```plantuml @startuml start repeat if (clause involve 0 synonym) then (yes) :query PKB if the clause holds; :REQUIRE clause holds; elseif (clause involve 1 unique synonym) then (yes) :query PKB to filter out candidates of this synonym that do not hold; :REQUIRE synonym still has candidates; endif repeatwhile (has remaining clause) is (yes) -> no; stop @enduml ``` SourceProc ```plantuml SourceProcessor->SourceProcessor: runLexer() activate SourceProcessor SourceProcessor->Lexer: run(source) activate Lexer Lexer-->SourceProcessor: tokens deactivate Lexer deactivate SourceProcessor SourceProcessor->SourceProcessor: runParser() activate SourceProcessor SourceProcessor->Parser: run(tokens) activate Parser Parser->PKBSetter: setRelations() activate PKBSetter PKBSetter-->Parser deactivate PKBSetter Parser-->SourceProcessor deactivate Parser ``` Flow of set cross procedure ```plantuml @startuml start :Set multi level call relations; :Set cross-procedure modify/use for all procedures; :Set cross-procedure modify/use for statements; stop @enduml ``` Interaction with PKB ```plantuml Parser->Parser: addNewStmt(statement_type, modifies, uses, constants, expression, called_procedure) activate Parser Parser->PKB: addNewEntity(statement_id, entity_type = statement, statement type) activate PKB PKB-->Parser: PKB_id of statement deactivate PKB Parser->Parser: addNewVars(uses, modifes) activate Parser loop for variables in uses/modifies Parser->PKB: addNewEntity(variable_name, entity_type = variable) activate PKB PKB-->Parser: PKB_id of variable deactivate PKB end deactivate Parser Parser->PKBSetter: setUseRelations(parent_statements, procedure_id, statement_id, used_variables) Parser->PKBSetter: setModifyRelations(parent_statements, procedure_id, statement_id, modified_variables) Parser->PKBSetter: setParentRelations(parent_statements, statement_id) Parser->PKBSetter: setFollowRelations(current_statement_list, statement_id) opt is a call statement Parser->PKBSetter: setCallRelations(current_procedure, called procedure) end opt statement requires pattern Parser->PKBSetter: setPattern(statement_id, expression) end deactivate Parser ``` setUseRelation() ```plantuml ->PKBSetter: setUse\nRelations(...) activate PKBSetter loop var in list of used variables loop par in list of parents PKBSetter->PKB: setUses(par_id, var_id) end PKBSetter->PKB: setUses(proc_id, var_id) PKBSetter->PKB: setUses(stmt_id, var_id) end deactivate PKBSetter ``` setModifyRelation() ```plantuml ->PKBSetter: setModify\nRelations(...) activate PKBSetter loop var in list of modified variables loop par in list of parents PKBSetter->PKB: setModifies(par_id, var_id) end PKBSetter->PKB: setModifies(proc_id, var_id) PKBSetter->PKB: setModifies(stmt_id, var_id) end deactivate PKBSetter ``` setFollowRelation() ```plantuml ->PKBSetter: setFollow\nRelations(...) activate PKBSetter loop other stmt in current stmt list alt is direct follow PKBSetter->PKB: setFollow(other_id, \nstmt_id, is_direct = TRUE) else is indirect follow PKBSetter->PKB: setFollow(other_id, \nstmt_id, is_direct = FALSE) end end deactivate PKBSetter ``` setParentRelation() ```plantuml ->PKBSetter: setParent\nRelations(...) activate PKBSetter loop par in list of parents alt is direct parent PKBSetter->PKB: setParent(par_id, \nstmt_id, is_direct = TRUE) else is indirect parent PKBSetter->PKB: setParent(par_id, \nstmt_id, is_direct = FALSE) end end deactivate PKBSetter ``` setPattern() ```plantuml ->PKBSetter: setPaternRelations(...) activate PKBSetter PKBSetter->ExpressionParser: extractAllASTTerm(expression) activate ExpressionParser ExpressionParser-->PKBSetter: list of AST terms deactivate ExpressionParser PKBSetter->PKBSetter: hash all terms PKBSetter->PKB: setPattern(statement_id, lhs_id,\n hashes_of_AST_terms, hashes_of_full_term) deactivate PKBSetter ``` ```plantuml @startuml class QueryObject { bool isSelectBool } QueryObject "1" *-- "*" Relation : contains QueryObject "1" *-- "*" With : contains QueryObject "1" *-- "*" Pattern : contains QueryObject "1" *-- "*" QueryResult : contains QueryObject "1" *-- "*" Synonym : contains @enduml ``` 1.2.3.2 ```plantuml @startuml start while (next token is of type Name?) if (following token after next token is "="?) then (yes) :assignment statement; else (no) switch (next token?) case (is "if") :if statement; case (is "while") :while statement; case (is "print") :print statement; case (is "read") :read statement; case (is "call") :call statement; endswitch endif :parse corresponding statement; endwhile (no) stop @enduml ``` parse Procedure ```plantuml @startuml start while (have token in deque?) if (following token after next token is "="?) then (yes) :assignment statement; else (no) switch (next token?) case (is "if") :if statement; case (is "while") :while statement; case (is "print") :print statement; case (is "read") :read statement; case (is "call") :call statement; endswitch endif :parse corresponding statement; endwhile (no) stop @enduml ``` cross-proc relation ```plantuml @startuml start while (for each procedure A) while (for each variable var used by a statement under procedure A) while (for each procedure B that directly/indirectly calls A) : set use/modify relation between B and var; endwhile (empty) endwhile (empty) endwhile (empty) stop @enduml ``` cross-proc relation 2 ```plantuml @startuml start while (for each call statement c that calls procedure A) :set use/modify between c and variables used/modified by A; while (for each direct/indirect parent statement s of c) :set use/modify relation between s and variables used/modified by A; endwhile (empty) endwhile (empty) stop @enduml ``` s1-s2 ```plantuml @startuml start while (for each call statement c that calls procedure A) :set use/modify between c and variables used/modified by A; while (for each direct/indirect parent statement s of c) :set use/modify relation between s and variables used/modified by A; endwhile (empty) endwhile (empty) stop @enduml ```