Algorithms Library Toolkit Core issueshttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues2023-04-16T10:18:00+02:00https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/235Improve Clang-Tidy check2023-04-16T10:18:00+02:00Ondřej ŠtorcImprove Clang-Tidy checkClang-Tidy can be invoked by adding
```cmake
set(CMAKE_CXX_CLANG_TIDY
clang-tidy)
```
to `CMakeLists.txt`.
This is better than the current solution, which doesn't recognize correct syntax. The current solution could be improved by ...Clang-Tidy can be invoked by adding
```cmake
set(CMAKE_CXX_CLANG_TIDY
clang-tidy)
```
to `CMakeLists.txt`.
This is better than the current solution, which doesn't recognize correct syntax. The current solution could be improved by adding these flags (not sure, I have quickly tried to do that, but with no success), but why duplicate these flags when we can invoke it with CMake?
The first step, however, is to fix the current errors or tune in the checks we want to care about.https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/232LatexConverter does not consider generates epsilon flag2022-05-16T11:44:24+02:00Tomáš PeckaLatexConverter does not consider generates epsilon flagConsider this automaton
```
DFA a b
><0 0 0
```
convert it to right rg
```
(RightRG nonterminalAlphabet = {0} terminalAlphabet = {a, b} initialSymbol = 0 rules = {(0, {a, b, (a, 0), (b, 0)})} generatesEpsilon = 1)
```
new initial symb...Consider this automaton
```
DFA a b
><0 0 0
```
convert it to right rg
```
(RightRG nonterminalAlphabet = {0} terminalAlphabet = {a, b} initialSymbol = 0 rules = {(0, {a, b, (a, 0), (b, 0)})} generatesEpsilon = 1)
```
new initial symbol should appear (and it appears in string::compose)
```
RIGHT_RG (
{0, 0'},
{a, b},
{ 0 -> a | a 0 | b | b 0,
0' -> | a | a 0 | b | b 0},
0')
```
but not in `LatexConverter`
```
$$G = (\{0\}, \{a, b\}, P, 0)$$ \\
\begin{array}{l}
P = \{\\
0 \rightarrow \varepsilon \mid a \mid a 0 \mid b \mid b 0 , \\
\}
\end{array}
```Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/231nullptr in abstraction::ValueHolder<object::Object>::getActualType) while usi...2022-10-19T21:50:22+02:00Tomáš Peckanullptr in abstraction::ValueHolder<object::Object>::getActualType) while using ValueHolder in evalAlgorithm helper as parameter for the second timeWe have found that the our webui code crashes with segfault.
* Webui version: https://gitlab.fit.cvut.cz/algorithms-library-toolkit/webui-client/commit/9e2da987b8f5fca6f51c98e197ae37ff1f266e40
* Core version: https://gitlab.fit.cvut.cz/...We have found that the our webui code crashes with segfault.
* Webui version: https://gitlab.fit.cvut.cz/algorithms-library-toolkit/webui-client/commit/9e2da987b8f5fca6f51c98e197ae37ff1f266e40
* Core version: https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/commit/00d54e0edfded9f60dc530cbae65e3fe7384fd91 but reproducible on current master as well.
I have simplified the code to the following MWE:
There are two functions, `test_full` which fully follows the ALT core calls made by our code that crashes and `test_mwe` which makes less algorithm evaluations but crashes in the same manner.
If you uncomment the highlighted line in `test_mwe` the code does not segfault. Is the function call doing something to the `ValueHolder` instance?
```cpp
#include <abstraction/TemporariesHolder.h>
#include <abstraction/ValueHolder.hpp>
#include <ast/command/EvalCommand.h>
#include <common/EvalHelper.h>
#include <ext/exception>
#include <global/GlobalData.h>
#include <iostream>
void test_full()
{
cli::Environment environment;
cli::EvalCommand registered("function mojeFunkce ( auto $mojepromenna ) returning auto begin\nreturn $mojepromenna;\nend");
registered.run(environment);
auto input = std::make_shared<abstraction::ValueHolder<std::string>>(std::string {"neco"}, true);
auto compose3 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {input}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
auto compose1 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {input}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
auto mojeFunk = abstraction::EvalHelper::evalAlgorithm(environment, "mojeFunkce", {}, {compose1}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
auto compose5 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {mojeFunk}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
auto compose4 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {mojeFunk}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
auto compose2 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {compose1}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
}
void test_mwe()
{
cli::Environment environment;
std::string foo("function mojeFunkce ( auto $mojepromenna ) returning auto begin\nreturn $mojepromenna;\nend");
environment.execute(std::make_shared<cli::StringLineInterface>(cli::StringLineInterface(foo)));
auto input = std::make_shared<abstraction::ValueHolder<std::string>>(std::string {"neco"}, true);
auto compose1 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {input}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
// commenting next line causes the code NOT to crash
auto mojeFunk = abstraction::EvalHelper::evalAlgorithm(environment, "mojeFunkce", {}, {compose1}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
// This is enough to crash, you don't have to call the following evalAlgorithm
// auto X = compose1->getActualType();
auto compose2 = abstraction::EvalHelper::evalAlgorithm(environment, "string::Compose", {}, {compose1}, abstraction::AlgorithmCategories::AlgorithmCategory::NONE);
}
int main()
{
try {
/* test_full(); */
test_mwe();
} catch (...) {
return alib::ExceptionHandler::handle(common::Streams::err);
}
}
```
```
$ bear -- g++ -g -fsanitize=address -std=c++20 -I/usr/include/algorithms-library -lalib2abstraction -lalib2std -lalib2common -lalib2cli -lalib2str test.cpp && ./a.out
AddressSanitizer:DEADLYSIGNAL
=================================================================
==1064921==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x7f899647f051 bp 0x607000010b28 sp 0x7ffe769b79b0 T0)
==1064921==The signal is caused by a READ memory access.
==1064921==Hint: address points to the zero page.
#0 0x7f899647f051 in object::Object::getId() const (/usr/lib/libalib2abstraction.so.0+0x48051)
#1 0x7f899647f17c in core::type_util<object::Object>::type(object::Object const&) (/usr/lib/libalib2abstraction.so.0+0x4817c)
#2 0x7f8996468041 in abstraction::ValueHolder<object::Object>::getActualType() const (/usr/lib/libalib2abstraction.so.0+0x31041)
#3 0x7f899646ff46 in abstraction::EvalHelper::evalAlgorithm(abstraction::TemporariesHolder&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, ext::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&, ext::vector<std::shared_ptr<abstraction::Value>, std::allocator<std::shared_ptr<abstraction::Value> > > const&, abstraction::AlgorithmCategories::AlgorithmCategory) (/usr/lib/libalib2abstraction.so.0+0x38f46)
#4 0x55c9d1162754 in test_mwe() /home/tomas/tmp/x/test.cpp:42
#5 0x55c9d1162f10 in main /home/tomas/tmp/x/test.cpp:49
#6 0x7f8995a2330f in __libc_start_call_main (/usr/lib/libc.so.6+0x2d30f)
#7 0x7f8995a233c0 in __libc_start_main@GLIBC_2.2.5 (/usr/lib/libc.so.6+0x2d3c0)
#8 0x55c9d115f494 in _start (/home/tomas/tmp/x/a.out+0x8494)
AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV (/usr/lib/libalib2abstraction.so.0+0x48051) in object::Object::getId() const
==1064921==ABORTING
```Jan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/226docs: string::Parse is missing grammar for some grammar types2022-04-07T18:34:33+02:00Tomáš Peckadocs: string::Parse is missing grammar for some grammar typeshttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/website/blob/362c0fd53468b63a1d85b9b292c2fb58e7f9b2fa/website/docs/parse.markdown#grammars
We only show RG and CFG.https://gitlab.fit.cvut.cz/algorithms-library-toolkit/website/blob/362c0fd53468b63a1d85b9b292c2fb58e7f9b2fa/website/docs/parse.markdown#grammars
We only show RG and CFG.https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/225string::Parse @Automaton fails with 0x20 (space) in the input alphabet2022-03-26T21:34:54+01:00Tomáš Peckastring::Parse @Automaton fails with 0x20 (space) in the input alphabet`string::Parse @Automaton` fails when trying to feed it with a space in the input alphabet.
`string::Compose` happily prints the space to the output...
```
> print NondeterministicApproximateSuffixAutomatonForHammingDistance "ah oj" 2 |...`string::Parse @Automaton` fails when trying to feed it with a space in the input alphabet.
`string::Compose` happily prints the space to the output...
```
> print NondeterministicApproximateSuffixAutomatonForHammingDistance "ah oj" 2 | string::Compose -
NFA a h j o
><(0, 0) (1, 1)|(2, 1)|(3, 0)|(4, 1)|(5, 1) (1, 0)|(2, 1)|(3, 1)|(4, 1)|(5, 1) (1, 1)|(2, 0)|(3, 1)|(4, 1)|(5, 1) (1, 1)|(2, 1)|(3, 1)|(4, 1)|(5, 0) (1, 1)|(2, 1)|(3, 1)|(4, 0)|(5, 1)
(...)
```
and it is not bothered by the fact that `string::Parse` can't deal with it
```
> print NondeterministicApproximateSuffixAutomatonForHammingDistance "ah oj" 2 | string::Compose - | string::Parse @Automaton -
0 [Standard exception]: Evaluation of algorithm string::Parse failed.
1 [Common exception]: Invalid line format
```
I guess that this `Bug | Feature` can be reproduced with other whitespace chars.
Found this while working on https://gitlab.fit.cvut.cz/algorithms-library-toolkit/webui-client/issues/48, webui parser suffers from the same issueJan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/224ci: Merge requests from external repos2022-02-01T17:21:54+01:00Tomáš Peckaci: Merge requests from external repos* The altbuilder jobs will get stuck because that runner is intentionally disabled for external repos
* Don't know yet how to live with that. Is there a way to "not-to-use" tag for external MRs?
* the package:docker job will fail becau...* The altbuilder jobs will get stuck because that runner is intentionally disabled for external repos
* Don't know yet how to live with that. Is there a way to "not-to-use" tag for external MRs?
* the package:docker job will fail because of `$CI_REGISTRY_IMAGE`
* resolve by tagging the image with some constant string and use that var only when pushing to registryTomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/223tests: size of linux pipes is limited2022-05-08T18:36:58+02:00Tomáš Peckatests: size of linux pipes is limitedWe use pipes in `TimeoutAqlTest`: The child spawns an aql interpreter which runs and the parent monitors it for timeouts. The childs stdout is redirected into a pipe with the second end of the pipe being managed (read) by parent.
The pa...We use pipes in `TimeoutAqlTest`: The child spawns an aql interpreter which runs and the parent monitors it for timeouts. The childs stdout is redirected into a pipe with the second end of the pipe being managed (read) by parent.
The parents waits in `select(2)` and does not read until child terminates. If the child wrote more than pipe buffer length bytes then the pipe might get full and a write call could block (and the child could timeout) until we read something out of the pipe.
See https://man7.org/linux/man-pages/man2/fcntl.2.html, section `Changing the capacity of a pipe`.
So we need to come up with a way how to continuously read from the pipe while waiting in select because of the timeout monitoring. Perhaps another thread which reads the data?Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/221bundle standard aql library2022-01-29T09:54:28+01:00Tomáš Peckabundle standard aql library* [ ] Create a simple aql script defining functions and procedures for standard usecases like "toMinimalDFA", "compareRegExps"
* [x] Install this aql script somewhere inside `/usr`, probably `/usr/lib/algorithms-library`
* [x] Load th...* [ ] Create a simple aql script defining functions and procedures for standard usecases like "toMinimalDFA", "compareRegExps"
* [x] Install this aql script somewhere inside `/usr`, probably `/usr/lib/algorithms-library`
* [x] Load this script in `aql2.cpp`
* [ ] Replace algorithms like `regexp::::ToAutomaton` which only wraps some default algos like `ToAutomatonGliushkov` with these functions when #222 done
- How to do this? We wanted to make `automaton::::Trim` a function from stdlib but we use it quite exstensively in tests. I think this is a problem of tests (our unit tests are not unit tests per se)
* [ ] How to bundle with webui? Move from aql to alib2cli?
Perhaps we can create more aql files, not just one.Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/220Investigate compilation performance with -ftime-trace2022-02-05T21:10:37+01:00Jan TrávníčekInvestigate compilation performance with -ftime-tracehttps://www.phoronix.com/scan.php?page=news_item&px=LLVM-Clang-9.0-Time-Tracehttps://www.phoronix.com/scan.php?page=news_item&px=LLVM-Clang-9.0-Time-TraceJan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/219idea: Autogenerate documentation by Doxygen2021-11-21T12:06:33+01:00Tomáš Peckaidea: Autogenerate documentation by DoxygenI think we could generate the actual documentation from the actual docstrings in the c++ code.
* Just let Doxygen do its magic before anything else happen. This outputs an XML
* Now, in compile time we should parse the XML and the `regi...I think we could generate the actual documentation from the actual docstrings in the c++ code.
* Just let Doxygen do its magic before anything else happen. This outputs an XML
* Now, in compile time we should parse the XML and the `registration` code from any `alib2algo` `.cpp` file should take what it needs from there.
However, can this be done in compile time or do we need to bundle the doxygen output and do this on library load by the CLI?Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/218LatexConverter - escape { and }2021-11-03T12:08:34+01:00Tomáš PeckaLatexConverter - escape { and }The braces are not print by LaTeX unless escaped with `\{`
```
\begin{tabular}{|rl||c|c|}
\hline
\multicolumn{2}{|c||}{DFA} & a & b\\\hline
& {} & {} & {} \\\hline
$\rightarrow$ & {A} & {A, B} & {B} \\\hline
...The braces are not print by LaTeX unless escaped with `\{`
```
\begin{tabular}{|rl||c|c|}
\hline
\multicolumn{2}{|c||}{DFA} & a & b\\\hline
& {} & {} & {} \\\hline
$\rightarrow$ & {A} & {A, B} & {B} \\\hline
& {A, B} & {A, B, C} & {B} \\\hline
& {A, B, C} & {A, B, C} & {B, D} \\\hline
& {B} & {C} & {} \\\hline
$\leftarrow$ & {B, D} & {C, D} & {D} \\\hline
& {C} & {} & {D} \\\hline
$\leftarrow$ & {C, D} & {D} & {D} \\\hline
$\leftarrow$ & {D} & {D} & {D} \\\hline
\end{tabular}
```Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/217build.sh: Enable passing cmake args2021-10-30T16:09:09+02:00Tomáš Peckabuild.sh: Enable passing cmake argsSo we can build with build.sh and specify custom options (like `-DCMAKE_INSTALL_PREFIX=`)So we can build with build.sh and specify custom options (like `-DCMAKE_INSTALL_PREFIX=`)Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/212Parser does not parse grammar with arithmetic symbols in input alphabet2021-02-06T20:14:41+01:00Tomáš PeckaParser does not parse grammar with arithmetic symbols in input alphabetThis does not work:
```
> print string::Parse @grammar::Grammar "CFG({S}, {+, *, (, )}, {S -> }, S)"
0 [Standard exception]: Evaluation of algorithm string::Parse failed.
1 [Common exception]: Parse callback not registered.
```
One has ...This does not work:
```
> print string::Parse @grammar::Grammar "CFG({S}, {+, *, (, )}, {S -> }, S)"
0 [Standard exception]: Evaluation of algorithm string::Parse failed.
1 [Common exception]: Parse callback not registered.
```
One has to replace the symbols with text symbols
```
> print string::Parse @grammar::Grammar "CFG({S}, {plus, star, lpar, rpar}, {S -> }, S)"
(CFG nonterminalAlphabet = {S}terminalAlphabet = {lpar, plus, rpar, star}initialSymbol = Srules = {(S, {[]})})
```
Possibly related to #209Jan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/210Text format for PDAs2021-05-13T14:29:24+02:00Tomáš PeckaText format for PDAsImplement a text (de)serializer for PDAs.
This can't be done with a simple table, so perhaps a raw list of transitions?
```
q a P O P -> r P U S H
```Implement a text (de)serializer for PDAs.
This can't be done with a simple table, so perhaps a raw list of transitions?
```
q a P O P -> r P U S H
```Jan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/209Automaton parser does not recognize `-` as a symbol of alphabet2021-05-13T14:29:37+02:00Tomáš PeckaAutomaton parser does not recognize `-` as a symbol of alphabet```
execute """
DFA b i - a g 1
> q0 q1 - - - - -
q1 - q2 - - - -
q2 - - q3 - - -
q3 - - - q4 - -
q4 - - - q5 q6 -
< q5 - - - - q7 -
< q6 - - - - - q8
""" | string::Parse ...```
execute """
DFA b i - a g 1
> q0 q1 - - - - -
q1 - q2 - - - -
q2 - - q3 - - -
q3 - - - q4 - -
q4 - - - q5 q6 -
< q5 - - - - q7 -
< q6 - - - - - q8
""" | string::Parse @Automaton -
```
this fails :( When i replace `-` with `x`, it works.Jan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/208EpsilonNPDA and NPDA in automaton run2020-11-29T20:50:59+01:00Jan TrávníčekEpsilonNPDA and NPDA in automaton runThe run of NPDA uses rudimental checking of visited configurations. This obviously fails in case there is an epsilon loop (or cycle) that increases the pushdown store height. No such issue would be with NPDA that would not allow epsilon ...The run of NPDA uses rudimental checking of visited configurations. This obviously fails in case there is an epsilon loop (or cycle) that increases the pushdown store height. No such issue would be with NPDA that would not allow epsilon transitions at all.
The proposed change is to rename NPDA to EpsilonNPDA and introduce NPDA type that does not allow epsilon transitions.Jan TrávníčekJan Trávníčekhttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/207ToCNF2021-02-21T13:57:14+01:00Tomáš PeckaToCNF`ToCNF` algorithm seems to handle the removal of epsilon-rules and unit-rules from the grammar, when the input is `CFG` or `EpsilonFreeCFG`.
Should this algorithm even perform this? I think we should consider checking for valid grammar...`ToCNF` algorithm seems to handle the removal of epsilon-rules and unit-rules from the grammar, when the input is `CFG` or `EpsilonFreeCFG`.
Should this algorithm even perform this? I think we should consider checking for valid grammar structure and then either throw an exception or convert to CNF. Do not invoke both (see for example `AutomatonComplement` and `Total`).https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/206ToCNF creates unreachable nonterminals2021-05-13T14:30:00+02:00Tomáš PeckaToCNF creates unreachable nonterminalsNonterminals `[0]` and `[1]` are unreachable in this example.
```
> execute string::Parse @Grammar "CFG ({A,B,C,D},
{0,1},
{
A -> B C | 0 | #E,
B -> B C | 0,
C -> C B | B C | 1,
D -> B D | 0 | 1
},
A)" | ToCNF - > $g
> print $g
(CNF nont...Nonterminals `[0]` and `[1]` are unreachable in this example.
```
> execute string::Parse @Grammar "CFG ({A,B,C,D},
{0,1},
{
A -> B C | 0 | #E,
B -> B C | 0,
C -> C B | B C | 1,
D -> B D | 0 | 1
},
A)" | ToCNF - > $g
> print $g
(CNF nonterminalAlphabet = {[A], [B], [C], [D], [0], [1]}terminalAlphabet = {0, 1}initialSymbol = [A]rules = {([A], {0, ([B], [C])}), ([B], {0, ([B], [C])}), ([C], {1, ([B], [C]), ([C], [B])}), ([D], {0, 1, ([B], [D])}), ([0], {0}), ([1], {1})}generatesEpsilon = 1)
```
According to BI-AAG slides we should create these nonterminals (that generate only one terminal) only when needed.Tomáš PeckaTomáš Peckahttps://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/202clang-format2022-05-08T13:23:58+02:00Tomáš Peckaclang-formatReview clang-format file (https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/blob/7b6245795da2da484dea81cfd10a19c0eac26c81/.clang-format)
You can test via [clang-format configurator](https://zed0.co.uk/clang-format-c...Review clang-format file (https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/blob/7b6245795da2da484dea81cfd10a19c0eac26c81/.clang-format)
You can test via [clang-format configurator](https://zed0.co.uk/clang-format-configurator/)Jan TrávníčekJan Trávníček2020-08-06https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/-/issues/200Indexes location2020-08-01T11:40:08+02:00Tomáš PeckaIndexes locationLooks like data structures for indexing are `alt::indexes::{stringology,arbology}` but algorithms are `alt::{arbology,stringology}::indexing`Looks like data structures for indexing are `alt::indexes::{stringology,arbology}` but algorithms are `alt::{arbology,stringology}::indexing`