---
# System prepended metadata

title: UML diagram docs

---

# 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
```