I was hoping to merge @Evil-Spirit changes to the solver that don't use Eigen as a separate PR. Then add Eigen after. I'm still on the fence about it because it's such a huge dependency, but a lot of work and discussion went into it. @rpavlik also made some changes that use Eigen, and I'm conflicted about those as well - he made many changes to ratpoly.cpp which is IMHO a very clean piece of code that should not get more complicated unless there is a good performance improvement - which there might be, I don't know.

All of this after version 3.0 of course ;-) The non-Eigen stuff I'd consider now, but even that still seems risky for an RC change.

It looks like libeigen uses OpenMP, and I wonder if it can also be used without OpenMP, so that is something to still figure out.

OpenMP is very non-invasive using a lot of #pragma that are just ignored if the compiler doesn't know what they are. I don't know if all of its features are implemented that way.

Trying this. I made a branch and applied all 9 patches. I can't do the submodule update for libeigen for some reason and it seems to be a local problem. Does this pass CI? I really want to try this ;-)

I'd squash the 2 commits that reintroduce flatbuffers and then remove it ;-) Or maybe all 3 eigen ones.

I'm not sure if this is the correct way to do this but I couldn't get it to build without the following:

diff --git a/src/solvespace.h b/src/solvespace.h
index 9c0cb9a..86d8dd6 100644
--- a/src/solvespace.h
+++ b/src/solvespace.h
@@ -30,6 +30,7 @@
 #include <unordered_set>
 #include <vector>
 
+#undef Success
 #define EIGEN_NO_DEBUG
 #include "SparseCore"

Related Issue: https://gitlab.com/libeigen/eigen/-/issues/253

Rebase latest master so CI can test this, also noticed this on macOS in the build log:

/Users/koen/Projects/solvespace/src/system.cpp:498:18: warning: comparison of integers of different signs: 'int' and 'std::__1::vector<SolveSpace::Equation *, std::__1::allocator<SolveSpace::Equation *> >::size_type' (aka 'unsigned long')
      [-Wsign-compare]
    for(i = 0; i < mat.eq.size(); i++) {
               ~ ^ ~~~~~~~~~~~~~

Btw, when I build this PR in Release mode, editing the heavy 8040 profile is butter smooth...
This is definitely a huge improvement.

EDIT: that was caused from me removing the cairo version information, because that broke the build for me, seems to be necessary on windows so I put it back and fixed the issue (cairo-version.h path which changed to src/cairo-version.h)

Btw, when I build this PR in Release mode, editing the heavy 8040 profile is butter smooth...
This is definitely a huge improvement.

That was the first thing I wanted to try. I'm hoping it will help will all linked sketches including IDF files with lots of detail and STL files.

EDIT: that was caused from me removing the cairo version information, because that broke the build for me, seems to be necessary on windows so I put it back and fixed the issue (cairo-version.h path which changed to src/cairo-version.h)

Why did a header file need to move?

Anyway, looks like Ubuntu failed. Oh wow. As I was writing this, the CI results disappeared right before my eyes. What's up with that? There was a CI report saying Ubuntu failed, macOS passed, and I think Windows passed, and now all that's left is "This branch has no conflicts...." Rebase and Merge. The page updated and removed the CI stuff as I was looking at it! The most recent CI result needs to stay ;-)

And now it's back.... Gone away while I was typing? odd...

I am working on this right now, and force pushed something, perhaps that messed things up? Still fixing some Ubuntu issues...

On linux, most stuff is installed through the system's package manager, so only a couple of "extlibs" are installed.
We forgot to add extlib/libeigen to that list on Ubuntu, hoping the last commit will fix the build.

Ok, now we are at /home/runner/work/solvespace/solvespace/extlib/libeigen/Eigen/src/Core/util/Constants.h:434:2: error: #error The preprocessor symbol 'Success' is defined, possibly by the X11 header file X.h

Used @kk6mrp's suggestion, this should be tested though, and if it doesn't work we will have to fork & patch libeigen to rename Success to something else...

We need to check the license situation with Eigen. It seems Eigen 2 was LGPLv3 which would be fine, and if I'm not mistaken can even be statically linked with GPLv3 code. Eigen 3.0 seems to be MPL licensed which I don't fully understand yet, but it claims to be GPL compatible?

Interesting, I'm not very knowledgable about licenses, hopefully someone else can chime in on that topic.

Also, there is this:

=================================================================
==10614==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 230144 byte(s) in 899 object(s) allocated from:
    #0 0x7f3ebb453608 in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xe0608)
    #1 0x564651553b55 in SolveSpace::List<SolveSpace::hParam>::ReserveMore(int) /home/runner/work/solvespace/solvespace/src/dsc.h:264
    #2 0x564651553b55 in SolveSpace::List<SolveSpace::hParam>::AllocForOneMore() /home/runner/work/solvespace/solvespace/src/dsc.h:276
    #3 0x564651553b55 in SolveSpace::List<SolveSpace::hParam>::Add(SolveSpace::hParam const*) /home/runner/work/solvespace/solvespace/src/dsc.h:281
    #4 0x564651553b55 in SolveSpace::Expr::ParamsUsedList(SolveSpace::List<SolveSpace::hParam>*) const /home/runner/work/solvespace/solvespace/src/expr.cpp:409

SUMMARY: AddressSanitizer: 230144 byte(s) leaked in 899 allocation(s).

@Evil-Spirit do you have any clue what's up here?

@jwesthues can you weigh in on Eigen being MPL licensed now and what if anything we need to do to use it?

As best I can tell, Eigen is distributed under the MPL 2.0, which gives us the following option:

3.3. Distribution of a Larger Work

You may create and distribute a Larger Work under terms of Your choice, provided that You also comply with the requirements of this License for the Covered Software. If the Larger Work is a combination of Covered Software with a work governed by one or more Secondary Licenses, and the Covered Software is not Incompatible With Secondary Licenses, this License permits You to additionally distribute such Covered Software under the terms of such Secondary License(s), so that the recipient of the Larger Work may, at their option, further distribute the Covered Software under the terms of either this License or such Secondary License(s).

Secondary Licenses are defined as

1.12. "Secondary License" means either the GNU General Public License, Version 2.0, the GNU Lesser General Public License, Version 2.1, the GNU Affero General Public License, Version 3.0, or any later versions of those licenses.

Our GPLv3 is a later version of the GPLv2, so I think our easiest option is to consider SolveSpace a Larger Work, and thus that the whole project (including Eigen as a component) may be distributed under the GPLv3. The MPL does give developers the option to designate MPL-licensed software as "Incompatible With Secondary Licenses" (in which case that wouldn't work), but Eigen doesn't seem to have done that so I think we're good.

1.12. "Secondary License" means either the GNU General Public License, Version 2.0, the GNU Lesser General Public License, Version 2.1, the GNU Affero General Public License, Version 3.0, or any later versions of those licenses.

Our GPLv3 is a later version of the GPLv2, so I think our easiest option is to consider SolveSpace a Larger Work, and thus that the whole project (including Eigen as a component) may be distributed under the GPLv3. The MPL does give developers the option to designate MPL-licensed software as "Incompatible With Secondary Licenses" (in which case that wouldn't work), but Eigen doesn't seem to have done that so I think we're good.

@jwesthues That sounds like a plausible interpretation to me. If I go by intent, I'm pretty sure our use is something they would want, but licenses... Eigen licensing looks like a mess to me, they have LGPL, BSD, MPL, Apache licenses all sitting there. I would say let's use it for the sparse matrix solving, but don't go using it all over the place. If something with cleaner licensing comes along we should switch to that.

For similar reasons, I'd like the evil spirit solver improvements in a separate PR. The first 1-5 don't need eigen, but don't compile on their own. The fixes must be later in the series? This is kind of a mess too.

We could look into finding another library that does the same?

There are a couple on the wikipedia page under "Software": https://www.wikiwand.com/en/Sparse_matrix

I also found this which looks pretty interesting: https://www.shapeop.org/index.php

And this: https://github.com/stevengj/nlopt

However, I am way out of my "comfort zone" here, it's a topic that interests me and I want to learn about but at the moment don't know much about at all. I really hope Evil-Spirit is willing to help with this =)

Unfortunately for the licensing point, Eigen is so well maintained and high quality that it has basically killed off all competitors in its realm: everybody uses it now. (I mean, some folks use GLM, but that's got a totally different niche.) The MPL2 usage is for a file-based copyleft, esssentially. Using some of the experimental addins (sparse support) might have other licenses, but you can do preprocessor defines based on what licenses you're OK with: #define EIGEN_MPL2_ONLY is one such option. (Though, that's mostly to exclude LGPL code... the MPL2 license is intended to be more permissive than their previous scheme.)

It's widely used by folks who are somewhat hesitant about copyleft sometimes, and the bulk of the license discussion is about how it's not copyleft: http://eigen.tuxfamily.org/index.php?title=Main_Page#License and quote "Virtually any software may use Eigen." They do have a discord server and mailing list if you want a clarification.

Given its maturity, at this point, I'd consider re-inventing the wheel and not using Eigen to be a poor use of time. Porting code to use eigen instead of homegrown implementations is probably an OK use of time: they're likely to be faster, and almost certainly better tested, if integrated correctly. tl;dr: I've used Eigen extensively for probably about 10 years by now, and it's still what I'd recommend

@vespakoen What shape is this in? If you squash the non-eigen commits into one, and the Eigen commits into another, I'll test and merge this soon.

It works, but it leaks memory, and I don't know where / how to fix it...

Splitting out the first 5 commits may help. Make a PR of those and another for the rest. Then we can also see which set causes the leak.

So I found what was leaking, but I also noticed some other leaks, and I think every time we use someVariable = {}; it leaks?

And by replacing it with someVariable.Clear(); it seems to not leak anymore.

(See: 363c74c#diff-39760e1093e53d3308df3f6e1fe078df19fa80c47142a58cf2baecf6b0944cdaL402)

I wonder if those other leaks I found were always there? or if they got introduced by this change, would be great if someone could enlighten me @phkahler @rpavlik @ruevs

Will check the master branch for leaks as well...

yeah, so using .Clear() in the right places is important for avoiding leaks, because lists and idlists share their backing storage by "reference" (a copy is just a shallow copy, and it depends on that in places), and there's no obvious/easy way to know if you're the last one using things generically. This is why I was trying to port to using a shared_ptr<vector> inside those classes because while there were no leaks at that time, they are very easy to introduce.

@vespakoen @rpavlik shall we close this now that #1158 and #1159 are merged?

Yeah let's close this, looks like only 1 commit didn't make it in, which fixed a couple probably small? leaks.

363c74c

Will make a new PR for this, probably by testing for leaks on the whole thing again.

I think I fixed that leak a different way, iirc. I did check the PRs I submitted recently with asan on Linux, while they weren't 100% leak free, they didn't add leaks.