section_2_4_4 and some questions

[chakpongchung]

section_2_4_4 and some questions

[murraycu]

It uses autotools. It also uses mm-commons in its autotools build files, but that is easily available, at least on Linux distros such as Ubuntu. But that's probably a little awkward for people on other platforms. I haven't made an effort to make this more generally useful.

I typically build and run the whole thing like so:
./autogen.sh --enable-warnings=fatal;make all check

Feel free to submit a PR that adds cmake support, for instance. I'll gladly merge it if it's nice and clean and obvious.

[murraycu]

But anyway, about the test failure: Yes, there seems to be a genuine problem that is visible when using g++, but which I didn't see when using clang++:

[murrayc@murrayc-ThinkPad-X220 murrayc-compiler-experiments (master)]$ valgrind --num-callers=50 ./section_2_4_4_minimal_dfa_with_hopcrofts_algorithm
==7737== Memcheck, a memory error detector
==7737== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7737== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==7737== Command: ./section_2_4_4_minimal_dfa_with_hopcrofts_algorithm
==7737==
Current partitions: {{s0, s1, s2, s4}, {s3, s5}}
Splitting on partition: {s0, s1, s2, s4}
==7737== Invalid read of size 8
==7737== at 0x11131C: std::_Sp_counted_base<(__gnu_cxx::_Lock_policy)2>::_M_release() (shared_ptr_base.h:155)
==7737== by 0x10F1D6: std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count() (shared_ptr_base.h:706)
==7737== by 0x10E09D: std::__shared_ptr<State, (__gnu_cxx::_Lock_policy)2>::__shared_ptr() (shared_ptr_base.h:1145)
==7737== by 0x10E0DF: std::shared_ptr::shared_ptr() (shared_ptr.h:103)
==7737== by 0x10B917: split(std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&, std::set<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > >, std::less<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > >, std::allocator<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:84)
==7737== by 0x10BF7D: construct_partitions(std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:158)
==7737== by 0x10CAAE: construct_minimal_dfa(std::shared_ptr const&, std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:268)
==7737== by 0x10CF7D: main (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:290)
==7737== Address 0x10 is not stack'd, malloc'd or (recently) free'd
==7737==
==7737==
==7737== Process terminating with default action of signal 11 (SIGSEGV)
==7737== Access not within mapped region at address 0x10
==7737== at 0x11131C: std::_Sp_counted_base<(__gnu_cxx::_Lock_policy)2>::_M_release() (shared_ptr_base.h:155)
==7737== by 0x10F1D6: std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count() (shared_ptr_base.h:706)
==7737== by 0x10E09D: std::__shared_ptr<State, (__gnu_cxx::_Lock_policy)2>::~__shared_ptr() (shared_ptr_base.h:1145)
==7737== by 0x10E0DF: std::shared_ptr::~shared_ptr() (shared_ptr.h:103)
==7737== by 0x10B917: split(std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&, std::set<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > >, std::less<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > >, std::allocator<std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:84)
==7737== by 0x10BF7D: construct_partitions(std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:158)
==7737== by 0x10CAAE: construct_minimal_dfa(std::shared_ptr const&, std::set<std::shared_ptr, std::less<std::shared_ptr >, std::allocator<std::shared_ptr > > const&) (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:268)
==7737== by 0x10CF7D: main (section_2_4_4_minimal_dfa_with_hopcrofts_algorithm.cc:290)
==7737== If you believe this happened as a result of a stack
==7737== overflow in your program's main thread (unlikely but
==7737== possible), you can try to increase the size of the
==7737== main thread stack using the --main-stacksize= flag.
==7737== The main thread stack size used in this run was 8388608.
==7737==
==7737== HEAP SUMMARY:
==7737== in use at exit: 2,240 bytes in 36 blocks
==7737== total heap usage: 64 allocs, 28 frees, 77,280 bytes allocated
==7737==
==7737== LEAK SUMMARY:
==7737== definitely lost: 0 bytes in 0 blocks
==7737== indirectly lost: 0 bytes in 0 blocks
==7737== possibly lost: 0 bytes in 0 blocks
==7737== still reachable: 2,240 bytes in 36 blocks
==7737== suppressed: 0 bytes in 0 blocks
==7737== Rerun with --leak-check=full to see details of leaked memory
==7737==
==7737== For counts of detected and suppressed errors, rerun with: -v
==7737== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
[murrayc@murrayc-ThinkPad-X220 murrayc-compiler-experiments (master)]$

[murraycu]

I think this is an appropriate fix, though it could be a bit cleaner: ceb393d