Pay another respect to kritacommand--which we are going beyond

Your work is gonna make Krita significantly different. – Wolthera, Krita developer and digital artist

Krita’s undo system, namely kritacommand, was added 8 years ago to Calligra under the name of kundo2, as a fork of Qt’s undo framework. The use of undo commands, however, might have an even longer history. Undo commands provide a way to revert individual actions. Up to now, most (though not all) undo commands do it by providing two sets of code that do and undo the actions, respectively. Drawbacks of this system includes (1) it is not very easy to manage; (2) it may introduce duplicated code; and (3) it makes it hard to access a previous document state without actually going back to that state. What I do is to start getting rid of such situation.

The plan for a new system is to use shallow copies to store documents at different states. Dmitry said “it was something we really want to do and allows us to make historical brushes (fetch content from earlier document states).” And according to him, he spent years to implement copy-on-write on paint layers. He suggested me to start from vector layers which he thought would be easier since it does not need to be very thread-safe.

I completely understood that was a challenge, but did not realize where the difficult part was until I come here. Copy-on-write is not the challenging part. We have QSharedDataPointer and almost all the work is to routinely replace the same code. Porting tools is more difficult. The old flake tools are running under the GUI thread, which makes no requirement on thread-safety. Technically we do not need to run it in a stroke / in image thread but with no multithreading the tools runs too slowly on some computers (read as “my Thinkpad laptop”) so I am not unwilling to take this extra challenge. In previous posts I described how the strokes work and the problems I encountered. Besides that there are still some problems I need to face.

the HACK code in the stroke strategy

At the last of the strokes post, I proposed a fix to the crash when deleting KisNode, which is messy. After testing with Dmitry at the sprint, we discovered that the real problems lies in KoShapeManager‘s updateTreeCompressor. It is used to schedule updates of its R-tree. However, it is run at the beginning of every other operation so Dmitry says it is no longer needed. After the compressor was removed we are safe to delete the node normally so there would be no need for such hack code.

Path tool crashing when editing calligraphic shapes

Calligraphic shapes, coming from Karbon, is a shape created by hand-drawing. It has many path points and editing it using path tool usually leads to a crash. Dmitry tested it with ASan and discovered the problem occurs because the path points, which is fetched in the GUI thread to paint the canvas, could be deleted when editing the shape. He suggests to apply a lock to the canvas, not allowing the image and GUI threads to access the shapes concurrently.

Keeping selections after undo/redoing

This challenge is a smaller one. The shape selections were not kept, since they are not part of the layer. It was owned by the layer’s shape manager, though, but a cloned layer would take a brand-new shape manager. In addition undo() and redo() will now replace the whole layer, so pointers to original shapes are no longer valid. This means merely keeping the selections from the shape manager would not work. The solution is to map the selected shapes to the cloned layer, which would be kept in the undo command. The strategy I use is similar to what we have done for layers: go through the whole heirarchy of the old layer and push everything into a queue; go through the heirarchy of the cloned layer in the same order and each time take the first shape in the queue; if the popped shape is in the selection, we add its counterpart in the cloned layer to our new selection.

For now the tools should be working and the merge request is prepared for final review. Hopefully it would make its way to master soon.

The Sprint

Hi -)) haven’t posted for some time, because I was busy travelling and coding for the first half of the month. From Aug 5 to Aug 9, I went to the Krita Sprint in Deventer, Netherlands.

According to Boud, I was the first person to arrive. My flight took a transit via Hong Kong where some flights were affected due to natural and social factors, but fortunately mine was not one of them. Upon arrival in Amsterdam I got a ticket for the Intercity to Deventer. Railway constructions made me take a transfer via Utrecht Centraal, but that was not a problem at all: the station has escalators going both up to the hall, and down to the platforms (in China you can only go to the hall by stairs or elevator (which is often crowded after you get off)). When I got out of Deventer Station, Boud immediately recognized me (how?!). It was early in the morning, and the street’s quietness was broken by the sound of me dragging my suitcase. Boud led me through Deventer’s crooked streets and alleys to his house.

For the next two days people gradually arrived. I met my main mentor Dmitry (magician!) and his tiger, Sagoskatt, which I (and many others) have mistaken for a giraffe. He was even the voice actor for Sago. He had got quite a lot of insights into the code base (according to Boud, “80%”) and solved a number of bugs in Krita (but he said he introduced a lot of bugs, ha!). Also I met David Revoy (my favourite painter!), the author of Pepper and Carrot. And Tiar, our developer who started to work full-time on Krita this year; she had always been volunteering to support other Krita users and always on the IRC and Reddit. And two of other three GSoC students for the year: Blackbeard (just as his face) and Hellozee. Sh_zam could not come and lost communications due to political issues, which was really unfortunate (eh at least now he can be connected). It is feels so good to be able to see so many people in the community – they are so nice! And it is such an experience to hack in a basement church.

On Aug 7 we went to the Open Air Museum. It displays a large extent of the history in the Netherlands, how their people lived. After a really delicious lunch we went out and started to do paintings. I was to paint on my Surface using Krita, but unfortunately it went out of battery so I had to gave up and painted on a postcard. The tram in the museum is my favourite one (I am always fond of transit) and they even have a carhouse where stood lots of old vehicles. Except for my head which hit the ceiling of the coach three times, everything that day was wonderful.

The next day was the main meeting. In the morning we discussed the development plans for Krita. Bugs. Stability. New features. David Revoy came up again with the docker size problem, which Boud simply called it “a Qt problem.” He said, “Yes I do know what to do with that, but new users probably don’t and thus we gotta address it and not solely blame Qt.” (Yeah it troubled me a lot as well!) Another thing closely related to me was building on Windows, which was largely neglected by KDE. In the afternoon the focus shifted to marketing. I did not know much about it, but it is a fact that we cannot produce electricity out of love. We spent quite a lot of time on the painting competition for Krita. Where it should be held. How to collect the paintings. How to filter out good pictures. Krita promotes new artists. They promote our software.

For the next two days people started leaving. I left on the 10th, and then slept for a whole day when I got to Nanjing (so tired…). On Aug 14th I left again for Toronto, and then restarted to write code and debug. I finally got the time to write this post today, as I finally fixed a crash in my project. It is almost finished, and soon another post would be made on it.

Strokes are Working Now

Okay, good news today. I have been porting DefaultTool to the new node-replacing system and it is working now, finally, at least for the part I have already done.

The work involves combining a number of different modules in Krita: the stroke system, KoInteractionTool and its interaction strategies, and, well, the COW mechanism in Flake.

KoInteractionTool is the class used to manage the interaction with vector shapes, and is subclassed by DefaultTool. The behaviours of KoInteractionTool (and thus DefaultTool) are defined by KoInteractionStrategys. Upon the press of the mouse button, DefaultTool creates an instance of some subclass of KoInteractionStrategy, say, ShapeMoveStrategy, according to the point of the click as well as keyboard modifiers. Mouse move events after that are all handled by the interaction strategy. When the mouse is released, the interaction strategy’s finishInteraction() is called, and then createCommand(). If the latter returns some KUndo2Command, the command is added to the undo history. Till now it sounds simple.

So how does the stroke system come in? I have experimented the interaction strategy without the stroke system (https://invent.kde.org/tusooaw/krita/commit/638bfcd84c622d3cfefda1e5132380439dd3fdc2), but it is really slow and even freezes Krita for a while sometimes. The stroke system allows the modification of the shapes to run in the image thread, instead of the GUI thread. A stroke is a set of jobs scheduled and run by a KisStrokesFacade (here, KisImage). One creates the stroke in a strokes facade using a stroke strategy, which defines the behaviour of the stroke. After creation, jobs can be added to the stroke and then executed at some later time (it is asynchronous).

So combining these two, we have an interaction strategy and a stroke strategy – when the interaction strategy is created, we start the stroke in the image; when there is mouse move, we add individual jobs that change the shapes to the stroke; when the mouse released, we end the stroke. My discussion with Dmitry firstly tended to make the interaction strategy inherit the stroke strategy but later it proves not a viable solution since the interaction strategy is owned and deleted by KoInteractionTool while the stroke strategy is owned by the stroke — which will lead to double deletion. So we divide it into two classes instead: the interaction strategy starts the stroke, and the stroke strategy takes a copy of the current active layer upon creation; when handling mouse move events, a job is added to the stroke to modify the current layer; finally when the interaction finishes, the interaction strategy ends the stroke and creates an undo command if the layer has been changed.

A problem I found lies in the final stage–if the mouse is released as soon as being pressed and no undo command is created, Krita will simply crash. It does not happen when I use gdb to start Krita so it seems to be a timing issue though it leads to difficulty for debugging as well. Dmitry used a self-modified version of Qt to produce a backtrace, indicating the problem probably lies in KisCanvas2‘s canvasUpdateCompressor, which is not thread-safe. However, after I changed it to KisThreadSafeSignalCompressor, the crash still happens, unfortunately.

The final inspiration comes from the comments in KisThreadSafeSignalCompressor, though. It indicates we cannot delete the compressor from other threads — we have to use obj->deleteLater() instead, since it lies in the gui thread. And aha, that is the problem. The stroke strategy’s destructor is executed in the image thread; if the undo command is not created, there is only one reference to our copied KisNode, namely in our stroke strategy, so it has to be destructed there. However, upon the creation of the KisNode, it is moved into the gui thread. So it simply means we cannot let it be deleted in the image thread. The solution looks a little bit messy, but it works:

1
2
3
4
5
KisNode *node = m_d->originalState.data(); // take the address from KisSharedPtr
node->ref(); // prevent KisSharedPtr from deleting the node
m_d->originalState.clear(); // now node is not being referenced by any KisSharedPtr
node->deref(); // the reference count is now zero again
node->deleteLater(); // it will be deleted by the event loop, later

`make -j5 kritaflake`

At the end of June I finished copy-on-write vector layers. From the very beginning, I have been researching into possibilities to make kritaflake implicitly sharable. In that post I mentioned the way Sean Parent uses for Photoshop, and adapted it for the derived d-pointers in Flake.

Derived d-pointers

TL;DR: We got rid of it.

As I mentioned in the task page, derived d-pointers originally in Flake are a barrier to implicit sharing. One of the reasons is that we need to write more code (either KisSharedDescendent wrapper class, or repeated code for virtual clone functions). Also, derived d-pointers do not actually encapsulate the data in the parent classes – for example, the members in KoShapePrivate are all accessible by descendents of KoShape, say, KoShapeContainer. That is probably not how encapsulating should work. So in the end we decided to get rid of derived d-pointers in Flake.

This leads to one problem, however, in the class KoShapeGroup. KoShapeGroup is a descendent of KoShapeContainer, which owns a KoShapeContainerModel that can be subclassed to control the behaviour when a child is added to or removed from the container. KoShapeGroup uses ShapeGroupContainerModel which performs additional operations specific to KoShapeGroup.

After I merged my branch into master, it was said that Flake tests failed under address sanitizer (ASan). I took a look and discovered that there was use after free in the class KoShapeGroup, namely the use of its d-pointer. The use is called by the destructor of KoShapeContainer, which calls KoShapeContainerModel::deleteOwnedShapes(), which removes individual shapes from the container, which then calls KoShapeGroup::invalidateSizeCache(). The original situation was:

  1. destructor of KoShapeGroup was called;
  2. members defined in KoShapeGroup got deleted (nothing, because everything is in the derived d-pointer which is defined in KoShape);
  3. destructor of KoShapeContainer was called, which calls d->model->deleteOwnedShapes();
  4. then that of KoShape, which deletes all the private members.

But after the derived d-pointers are converted to normal ones, the calling sequence upon destruction becomes:

  1. destructor of KoShapeGroup was called;
  2. members defined in KoShapeGroup got deleted (its own d-pointer);
  3. destructor of KoShapeContainer was called, which calls d->model->deleteOwnedShapes();
  4. d->model is a ShapeGroupContainerModel, which will call KoShapeGroup::invalidateSizeCache();
  5. that last function accesses the d-pointer of KoShapeGroup, USE AFTER FREE.

In order to solve this problem we have to manually call model()->deleteOwnedShapes() in the destructor of KoShapeGroup, at which time the d-pointer is still accessible.

q-pointers

TL;DR: We also got rid of it.

q-pointers are a method used in Qt to hide private methods from the header files, in order to improve binary compatibility. q-pointers are stored in *Private classes (ds), indicating the object that owns this private instance. But this is, of course, conflicting with the principle of “sharing” because the situation now is that multiple objects can own the same data. The q-pointers in flake is rather confusing under such circumstances, since the private data cannot know which object is the caller.

To avoid this confusion, there are multiple ways:

  1. to move all the functions regarding q-pointers to the public classes;
  2. to pass the q-pointer every time when calling those functions in private classes; or
  3. to add another layer of “shared data” in the d-pointer and keep the q-pointers in the unshared part.

implicit sharing

To enable implicit sharing for the KoShape hierarchy, the only thing left to be done is to change the QScopedPointer<Private> d; in the header file to QSharedDataPointer<Private> d; and make the private classes inherit QSharedData. This step is rather easy and then just run the tests to make sure it does not break anything. Horray!

Snapshot Docker

Over the past few weeks I have been working on the Snapshot Docker, and now it is finished already. -))

The idea of snapshots is to make copies of the current document and allow users to return to them at a later time. This is a part of my whole Google Summer of Code project, which aims to bring Krita a better undo/redo system. When fully implemented, it will fully replace the current mechanism that stores actions with one that stores different states. That is to say, Krita will create a snapshot of the document for every undoable step.

Snapshot Docker is not only a feature requested by artists but also a experimental implementation of the clone-replace mechanism. It has the following key parts:

  1. Cloning the document, which is provided by KisDocument::lockAndCloneForSaving(), which is already implemented in master.

  2. Replace the current document by another one, which is previously cloned.

Part (1) is already implemented so the work falls mainly on Part (2). My original approach is to replace the document and image pointers in KisView and KisCanvas, but it is not viable since other parts of the program have signal/slot connections on the KisDocument and KisImage, and directly replacing the two pointers will not only fail to work but also cause weird crashes. After discussing with Dmitry, we find out that it is probably better not to touch these two pointers, but to replace the content within KisDocument and KisImage. It is therefore suggested that two member functions be made, namely KisDocument::copyFromDocument and KisImage::copyFromImage. These functions copies data from another document/image to the current one, avoiding the changes to the pointers inside the original instance. Eh, except for the nodes, since we have to reset and refresh the nodes in the image.

It is also important to notify other parts of Krita about the change in the document. One important thing is tell the layer docker about the changes in the nodes (they are completely different), which is done using the KisImage::sigLayersChangedAsync() signal. The current activated node is also stored and restored, by using the strategy of linearizing the layer tree using a queue, and then finding the corresponding node in the cloned image. Note that when restoring, we are unable to find layer by uuid, since they should change when copied to the current image (the comments in KisImage says the only situation where we should keep the uuids is for saving).

Another interesting thing is the palettes. Krita 4.2.0 allows documents to store their own, local palettes. The palette list is but a QList<KoColorSet *>, meaning that only creating a new QList of the same pointers will not work. This is because, the palettes are controlled by canvas resource manager, which takes the responsibility to delete them. Therefore, when taking snapshots, we had better take deep copies of the KoColorSets. And then another problem comes: the snapshots own their KoColorSets because they are not controlled by the resource manager in any way; but the KisDocument in the view does not. So we have to set up another flag, ownsPaletteList, to tell the document whether it should delete the palettes in the destructor.

And now the work has shifted to the refactoring of kritaflake, the library that mainly handles vector layers and shapes. I converted the whole KoShape hierarchy to implicit sharing where possible, but some tests are broken. I am now on Windows, where unit tests do not run. I will continue the development of flake as soon as I get access to my Linux laptop.

New Style Signal/Slot Connection

Yes, I know. The last post on the assistants is rather boring. And yet these days I have been working on the snapshot docker, though it still seems a little (just a little, you see) unfinished as Dmitry is said to experience a relatively high delay when switching between snapshots. However this is not what I can reproduce on my older laptop, so I am really waiting for his test results in order to further investigate the problem.

But there is something interesting happening just when I am randomly testing things. From Krita’s debug output, I saw QObject::connect() complaining about the arguments I passed, saying it is expecting parenthesis. “Okay,” I thought, “then there have to be something wrong with the code I wrote.” And that was quite confusing. I remember having used member function pointers in those places, got a compile-time error since KisSignalAutoConnectionsStore did not support the new syntax, then switched back to the SINGAL() and SLOT() macros. KisSignalAutoConnectionsStore is a helper class to quickly (dis)connect a group of connections. One can use the addConnection() method to add a connection, and use clear() to remove all connections made before.

Well, everything good, apart from the fact that I missed the parenthesis, which I did not discover until I looked into the debug output. So I asked Dmitry why not add the new syntax to KisSignalAutoConnectionsStore, and he said we should.

What is good about the new syntax is compile-time checking. We probably do not want our connections to fail to be made only when you run the program, just because there is a typo in the signature. That is definitely tiring and hard to catch (hmm, I did not notice the problem until today I randomly glanced at the command line; it might be worse if I shipped the snapshot docker together with those careless bugs).

The modification to the code seems straightforward. All what happens is in the KisSignalAutoConnection class. In its constructor, the connection is made using QObject::connect(); in its destructor, the connection is removed by passing the same sets of arguments to QObject::disconnect() currently in master. The signature is just KisSignalAutoConnection(const QObject *, const char *, const QObject *, const char *), as SIGNAL() and SLOT() macros are but to append their arguments to the string "1" and "2" respectively.

So the problem we have is we do not want the arguments that specify the signals and/or slots to be just strings. We want them to be pointers to member functions, or maybe lambdas. According to QObject document, the signature for new-style connect() is:

1
QMetaObject::Connection QObject::connect(const QObject *sender, PointerToMemberFunction signal, const QObject *context, Functor functor, Qt::ConnectionType type = Qt::AutoConnection)

Okay, so we know that sender and receiver should be pointers to QObjects, and either the type of signal or functor we do not know. Now let’s make our KisSignalAutoConnection constructor a template function:

1
2
3
4
template<class Signal, class Method>
inline KisSignalAutoConnection(const QObject *sender, Signal signal,
const QObject *receiver, Method method
Qt::ConnectionType type = Qt::AutoConnection);

But when these parameters are passed to QObject::connect(), we get a compile-time error, saying there is no matching overload for connect().

Why?

The answer is the Qt documentation is simplifying, if not hiding, the truth. The real definition for connect() is found in Line 227 of qobject.h:

1
2
3
4
template <typename Func1, typename Func2>
static inline QMetaObject::Connection connect(const typename QtPrivate::FunctionPointer<Func1>::Object *sender, Func1 signal,
const typename QtPrivate::FunctionPointer<Func2>::Object *receiver, Func2 slot,
Qt::ConnectionType type = Qt::AutoConnection)

And tracking down the definition of QtPrivate::FunctionPointer, we get it in qobjectdefs_impl.h:

1
2
3
4
5
template<class Obj, typename Ret, typename... Args> struct FunctionPointer<Ret (Obj::*) (Args...)>
{
typedef Obj Object;
...
};

And seeing what we have passed to KisSignalAutoConnection (in the test code):

1
2
KisSignalAutoConnectionsStore conn;
conn.addConnection(test1.data(), &TestClass::sigTest1, test2.data(), &TestClass::slotTest1);

We can see that Func1 is a member function of TestClass, so QtPrivate::FunctionPointer<Func1>::Object is just TestClass. But the constructor of KisSignalAutoConnection receives a const QObject *. The problem here is that connect() is expecting a const TestClass *, but we give them a const QObject *. A base class pointer cannot be implicitly converted to a derived class pointer, so we have that error.

The resolution seems pretty simple, as we only need to include the types of sender and receiver into the template, and pass everything as-is to QObject::connect():

1
2
3
template<class Sender, class Signal, class Receiver, class Method>
inline KisSignalAutoConnection(Sender sender, Signal signal, Receiver receiver, Method method,
Qt::ConnectionType type = Qt::AutoConnection);

Sounds viable. But how can we store the four parameters? It might be intuitive to make another base class, say, KisSignalAutoConnectionBase(), and make KisSignalAutoConnection a template class, so we can store sender, receiver, etc.

But wait, isn’t this just too complex? First of all, we do not have any overridden functions except for the destructor. What is more, we do not seem to have any valuable things in that base class – it would be an empty class. The use of inheritance here is ugly and useless.

And, we do not need to store the four parameters at all. QObject::connect() returns a QMetaObject::Connection, which can be used later to disconnect() it. So instead of the parameters passed to connect(), we just store the Connection object. And that is not part of the template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public:
template<class Sender, class Signal, class Receiver, class Method>
inline KisSignalAutoConnection(Sender sender, Signal signal, Receiver receiver, Method method,
Qt::ConnectionType type = Qt::AutoConnection)
: m_connection(QObject::connect(sender, signal, receiver, method, type))
{
}

inline ~KisSignalAutoConnection()
{
QObject::disconnect(m_connection);
}

private:
QMetaObject::Connection m_connection;

And with the test code mentioned above, we do make sure that the new implementation works well with both syntaxes.

So, great, krita developers, we can use the new syntax for auto connections as well.

PS: There will soon be another post on my work of the snapshot docker – it’s almost finished!

Assistants -- copy, share, assignment

Over the last week I have been investigating into Bug 361012, on the undo history of the modification of guides. But from the very beginning I mixed up the two terms “guides” and “assistants,” so I decided to work on both. The work with guides is a lot simpler and will not be covered here, though.

As I write this post, the master branch of Krita does not create any undo commands for the document. I first added undo commands for adding and removing assistants, which seems the easiest. The editing of them is a bit more difficult, as the dragging operations involve the movement of many “handles,” the movable round buttons that define the position of one or more assistants. The source code on master for implementing such actions is quite complicated and involves a great number of cases. It would be another great endeavour to put all these bunches of code into a KUndo2Command. But, another thing I have experimented with and I will be working on will immediately clear the clouds.

So I just thought of the copy-on-write mechanism, and yes, why not? Though COW itself is not actually implemented for the guides, it does seem inspiring. I mean, we can just save a copy of all assistants and, when needed, restore that.

The main problem here is the handles. They are represented as shared pointers in individual assistants and may be shared between different ones (e.g. two perspectives share two corner handles and one side handles). When we take a clone of the list of assistants it will be necessary to keep this kind of relationship. My solution is to use a QMap of pointers, which seems to coincide with the logic of exporting to xml, but I had yet to read that part of the code when writing mine so I did not know about that. The logic is to check, for every handle, whether there is a mapping relationship in the map. If there is, we reuse that handle, and if not, we create a new one with the same position and record that relationship in our QMap.

But some display properties are not to be recorded into the undo history. Such properties include the changing of color, visibility, etc. To resolve this problem, I put these data into a shared pointer and, when we are cloning an assistant for undo/redo, we will reuse that pointer. When we replace the assistant list with the one recorded, all the display properties will remain since the data are shared.

And for the next several weeks I will move onto the Snapshot Docker.

Polymorphism and Implicit Sharing

Recently I have been researching into possibilities to make members of KoShape copy-on-write. At first glance, it seems enough to declare d-pointers as some subclass of QSharedDataPointer (see Qt’s implicit sharing) and then replace pointers with instances. However, there remain a number of problems to be solved, one of them being polymorphism.

polymorphism and value semantics

In the definition of KoShapePrivate class, the member fill is stored as a QSharedPointer:

QSharedPointer<KoShapeBackground> fill;

There are a number of subclasses of KoShapeBackground, including KoColorBackground, KoGradientBackground, to name just a few. We cannot store an instance of KoShapeBackground directly since we want polymorphism. But, well, making KoShapeBackground copy-on-write seems to have nothing to do with whether we store it as a pointer or instance. So let’s just put it here – I will come back to this question at the end of this post.

d-pointers and QSharedData

The KoShapeBackground heirarchy (similar to the KoShape one) uses derived d-pointers for storing private data. To make things easier, I will here use a small example to elaborate on its use.

derived d-pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class AbstractPrivate
{
public:
AbstractPrivate() : var(0) {}
virtual ~AbstractPrivate() = default;

int var;
};

class Abstract
{
public:
// it is not yet copy-constructable; we will come back to this later
// Abstract(const Abstract &other) = default;
~Abstract() = default;
protected:
explicit Abstract(AbstractPrivate &dd) : d_ptr(&dd) {}
public:
virtual void foo() const = 0;
virtual void modifyVar() = 0;
protected:
QScopedPointer<AbstractPrivate> d_ptr;
private:
Q_DECLARE_PRIVATE(Abstract)
};

class DerivedPrivate : public AbstractPrivate
{
public:
DerivedPrivate() : AbstractPrivate(), bar(0) {}
virtual ~DerivedPrivate() = default;

int bar;
};

class Derived : public Abstract
{
public:
Derived() : Abstract(*(new DerivedPrivate)) {}
// it is not yet copy-constructable
// Derived(const Derived &other) = default;
~Derived() = default;
protected:
explicit Derived(AbstractPrivate &dd) : Abstract(dd) {}
public:
void foo() const override { Q_D(const Derived); cout << "foo " << d->var << " " << d->bar << endl; }
void modifyVar() override { Q_D(Derived); d->var++; d->bar++; }
private:
Q_DECLARE_PRIVATE(Derived)
};

The main goal of making DerivedPrivate a subclass of AbstractPrivate is to avoid multiple d-pointers in the structure. Note that there are constructors taking a reference to the private data object. These are to make it possible for a Derived object to use the same d-pointer as its Abstract parent. The Q_D() macro is used to convert the d_ptr, which is a pointer to AbstractPrivate to another pointer, named d, of some of its descendent type; here, it is a DerivedPrivate. It is used together with the Q_DECLARE_PRIVATE() macro in the class definition and has a rather complicated implementation in the Qt headers. But for simplicity, it does not hurt for now to understand it as the following:

#define Q_D(Class) Class##Private *const d = reinterpret_cast<Class##Private *>(d_ptr.data())

where Class##Private means simply to append string Private to (the macro argument) Class.

Now let’s test it by creating a pointer to Abstract and give it a Derived object:

1
2
3
4
5
6
7
int main()
{
QScopedPointer<Abstract> ins(new Derived());
ins->foo();
ins->modifyVar();
ins->foo();
}

Output:

foo 0 0
foo 1 1

Looks pretty viable – everything’s working well! – What if we use Qt’s implicit sharing? Just make AbstractPrivate a subclass of QSharedData and replace QScopedPointer with QSharedDataPointer.

making d-pointer QSharedDataPointer

In the last section, we commented out the copy constructors since QScopedPointer is not copy-constructable, but here QSharedDataPointer is copy-constructable, so we add them back:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class AbstractPrivate : public QSharedData
{
public:
AbstractPrivate() : var(0) {}
virtual ~AbstractPrivate() = default;

int var;
};

class Abstract
{
public:
Abstract(const Abstract &other) = default;
~Abstract() = default;
protected:
explicit Abstract(AbstractPrivate &dd) : d_ptr(&dd) {}
public:
virtual void foo() const = 0;
virtual void modifyVar() = 0;
protected:
QSharedDataPointer<AbstractPrivate> d_ptr;
private:
Q_DECLARE_PRIVATE(Abstract)
};

class DerivedPrivate : public AbstractPrivate
{
public:
DerivedPrivate() : AbstractPrivate(), bar(0) {}
virtual ~DerivedPrivate() = default;

int bar;
};

class Derived : public Abstract
{
public:
Derived() : Abstract(*(new DerivedPrivate)) {}
Derived(const Derived &other) = default;
~Derived() = default;
protected:
explicit Derived(AbstractPrivate &dd) : Abstract(dd) {}
public:
void foo() const override { Q_D(const Derived); cout << "foo " << d->var << " " << d->bar << endl; }
void modifyVar() override { Q_D(Derived); d->var++; d->bar++; }
private:
Q_DECLARE_PRIVATE(Derived)
};

And testing the copy-on-write mechanism:

1
2
3
4
5
6
7
8
9
int main()
{
QScopedPointer<Derived> ins(new Derived());
QScopedPointer<Derived> ins2(new Derived(*ins));
ins->foo();
ins->modifyVar();
ins->foo();
ins2->foo();
}

But, eh, it’s a compile-time error.

error: reinterpret_cast from type 'const AbstractPrivate*' to type 'AbstractPrivate*' casts away qualifiers
 Q_DECLARE_PRIVATE(Abstract)

Q_D, revisited

So, where does the const removal come from? In qglobal.h, the code related to Q_D is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> inline T *qGetPtrHelper(T *ptr) { return ptr; }
template <typename Ptr> inline auto qGetPtrHelper(const Ptr &ptr) -> decltype(ptr.operator->()) { return ptr.operator->(); }

// The body must be a statement:
#define Q_CAST_IGNORE_ALIGN(body) QT_WARNING_PUSH QT_WARNING_DISABLE_GCC("-Wcast-align") body QT_WARNING_POP
#define Q_DECLARE_PRIVATE(Class) \
inline Class##Private* d_func() \
{ Q_CAST_IGNORE_ALIGN(return reinterpret_cast<Class##Private *>(qGetPtrHelper(d_ptr));) } \
inline const Class##Private* d_func() const \
{ Q_CAST_IGNORE_ALIGN(return reinterpret_cast<const Class##Private *>(qGetPtrHelper(d_ptr));) } \
friend class Class##Private;

#define Q_D(Class) Class##Private * const d = d_func()

It turns out that Q_D will call d_func() which then calls an overload of qGetPtrHelper() that takes const Ptr &ptr. What does ptr.operator->() return? What is the difference between QScopedPointer and QSharedDataPointer here?

QScopedPointer‘s operator->() is a const method that returns a non-const pointer to T; however, QSharedDataPointer has two operator->()s, one being const T* operator->() const, the other T* operator->(), and they have quite different behaviours – the non-const variant calls detach() (where copy-on-write is implemented), but the other one does not.

qGetPtrHelper() here can only take d_ptr as a const QSharedDataPointer, not a non-const one; so, no matter which d_func() we are calling, we can only get a const AbstractPrivate *. That is just the problem here.

To resolve this problem, let’s replace the Q_D macros with the ones we define ourselves:

#define CONST_SHARED_D(Class) const Class##Private *const d = reinterpret_cast<const Class##Private *>(d_ptr.constData())
#define SHARED_D(Class) Class##Private *const d = reinterpret_cast<Class##Private *>(d_ptr.data())

We will then use SHARED_D(Class) in place of Q_D(Class) and CONST_SHARED_D(Class) for Q_D(const Class). Since the const and non-const variant really behaves differently, it should help to differentiate these two uses. Also, delete Q_DECLARE_PRIVATE since we do not need them any more:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class AbstractPrivate : public QSharedData
{
public:
AbstractPrivate() : var(0) {}
virtual ~AbstractPrivate() = default;

int var;
};

class Abstract
{
public:
Abstract(const Abstract &other) = default;
~Abstract() = default;
protected:
explicit Abstract(AbstractPrivate &dd) : d_ptr(&dd) {}
public:
virtual void foo() const = 0;
virtual void modifyVar() = 0;
protected:
QSharedDataPointer<AbstractPrivate> d_ptr;
};

class DerivedPrivate : public AbstractPrivate
{
public:
DerivedPrivate() : AbstractPrivate(), bar(0) {}
virtual ~DerivedPrivate() = default;

int bar;
};

class Derived : public Abstract
{
public:
Derived() : Abstract(*(new DerivedPrivate)) {}
Derived(const Derived &other) = default;
~Derived() = default;
protected:
explicit Derived(AbstractPrivate &dd) : Abstract(dd) {}
public:
void foo() const override { CONST_SHARED_D(Derived); cout << "foo " << d->var << " " << d->bar << endl; }
void modifyVar() override { SHARED_D(Derived); d->var++; d->bar++; }
};

With the same main() code, what’s the result?

foo 0 0
foo 1 16606417
foo 0 0

… big whoops, what is that random thing there? Well, if we use dynamic_cast in place of reinterpret_cast, the program simply crashes after ins->modifyVar();, indicating that ins‘s d_ptr.data() is not at all a DerivedPrivate.

virtual clones

The detach() method of QSharedDataPointer will by default create an instance of AbstractPrivate regardless of what the instance really is. Fortunately, it is possible to change that behaviour through specifying the clone() method.

First, we need to make a virtual function in AbstractPrivate class:

virtual AbstractPrivate *clone() const = 0;

(make it pure virtual just to force all subclasses to re-implement it; if your base class is not abstract you probably want to implement the clone() method) and then override it in DerivedPrivate:

virtual DerivedPrivate *clone() const { return new DerivedPrivate(*this); }

Then, specify the template method for QSharedDataPointer::clone(). As we will re-use it multiple times (for different base classes), it is better to define a macro:

1
2
3
4
5
6
7
#define DATA_CLONE_VIRTUAL(Class) template<>                      \
Class##Private *QSharedDataPointer<Class##Private>::clone() \
{ \
return d->clone(); \
}
// after the definition of Abstract
DATA_CLONE_VIRTUAL(Abstract)

It is not necessary to write DATA_CLONE_VIRTUAL(Derived) as we are never storing a QSharedDataPointer<DerivedPrivate> throughout the heirarchy.

Then test the code again:

foo 0 0
foo 1 1
foo 0 0

– Just as expected! It continues to work if we replace Derived with Abstract in QScopedPointer:

QScopedPointer<Abstract> ins(new Derived());
QScopedPointer<Abstract> ins2(new Derived(* dynamic_cast<const Derived *>(ins.data())));

Well, another problem comes, that the constructor for ins2 seems too ugly, and messy. We could, like the private classes, implement a virtual function clone() for these kinds of things, but it is still not gentle enough, and we cannot use a default copy constructor for any class that contains such QScopedPointers.

What about QSharedPointer that is copy-constructable? Well, then these copies actually point to the same data structures and no copy-on-write is performed at all. This still not wanted.

the Descendents of …

Inspired by Sean Parent’s video, I finally come up with the following implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template<typename T>
class Descendent
{
struct concept
{
virtual ~concept() = default;
virtual const T *ptr() const = 0;
virtual T *ptr() = 0;
virtual unique_ptr<concept> clone() const = 0;
};
template<typename U>
struct model : public concept
{
model(U x) : instance(move(x)) {}
const T *ptr() const { return &instance; }
T *ptr() { return &instance; }
// or unique_ptr<model<U> >(new model<U>(U(instance))) if you do not have C++14
unique_ptr<concept> clone() const { return make_unique<model<U> >(U(instance)); }
U instance;
};

unique_ptr<concept> m_d;
public:
template<typename U>
Descendent(U x) : m_d(make_unique<model<U> >(move(x))) {}

Descendent(const Descendent & that) : m_d(move(that.m_d->clone())) {}
Descendent(Descendent && that) : m_d(move(that.m_d)) {}

Descendent & operator=(const Descendent &that) { Descendent t(that); *this = move(t); return *this; }
Descendent & operator=(Descendent && that) { m_d = move(that.m_d); return *this; }

const T *data() const { return m_d->ptr(); }
const T *constData() const { return m_d->ptr(); }
T *data() { return m_d->ptr(); }
const T *operator->() const { return m_d->ptr(); }
T *operator->() { return m_d->ptr(); }
};

This class allows you to use Descendent<T> (read as “descendent of T“) to represent any instance of any subclass of T. It is copy-constructable, move-constructable, copy-assignable, and move-assignable.

Test code:

1
2
3
4
5
6
7
8
9
int main()
{
Descendent<Abstract> ins = Derived();
Descendent<Abstract> ins2 = ins;
ins->foo();
ins->modifyVar();
ins->foo();
ins2->foo();
}

It gives just the same results as before, but much neater and nicer – How does it work?

First we define a class concept. We put here what we want our instance to satisfy. We would like to access it as const and non-const, and to clone it as-is. Then we define a template class model<U> where U is a subclass of T, and implement these functionalities.

Next, we store a unique_ptr<concept>. The reason for not using QScopedPointer is QScopedPointer is not movable, but movability is a feature we actually will want (in sink arguments and return values).

Finally it’s just the constructor, moving and copying operations, and ways to access the wrapped object.

When Descendent<Abstract> ins2 = ins; is called, we will go through the copy constructor of Descendent:

Descendent(const Descendent & that) : m_d(move(that.m_d->clone())) {}

which will then call ins.m_d->clone(). But remember that ins.m_d actually contains a pointer to model<Derived>, whose clone() is return make_unique<model<Derived> >(Derived(instance));. This expression will call the copy constructor of Derived, then make a unique_ptr<model<Derived> >, which calls the constructor of model<Derived>:

model(Derived x) : instance(move(x)) {}

which move-constructs instance. Finally the unique_ptr<model<Derived> > is implicitly converted to unique_ptr<concept>, as per the conversion rule. “If T is a derived class of some base B, then std::unique_ptr<T> is implicitly convertible to std::unique_ptr<B>.”

And from now on, happy hacking — (.>w<.)

GSoC 2019

This summer will be a little bit interesting as I joined the Google Summer of Code (GSoC). The software I will be working on is Krita. Krita is a painting software I have been using for more than one year. Since the (pre)release of Krita 4.0, I use it to paint all my works.

Before using Krita, I used to use PaintToolSAI, and there are quite a lot of concepts and functionalities in it that I find really useful; after getting involved in the Krita community I am pretty lucky to be able to introduce these little shiny stars to our community, and even implement some of them.

My project for GSoC is on the undo/redo system in Krita. The system currently works using an undo stack to storage individual changes to the document, and invoking these commands to perform undos and redos. This system is complex and not easy to maintain. As Dmitry suggests, a better solution would be storing the states of the document as shallow copies, since it simplifies the system and make history brushes possible. It would be a rather huge and fundamental change in the code, and he recommends me to experiment with vector layers first.

Another part of the project, which is not a research, is the snapshot docker that would allow users to temporarily save some states of the document and return to them quickly at a later time. This is an enhancement on the GUI level, as the tile data in paint layers are shallow copied, making it possible to make a clone of the document relatively fast.

I will make more posts on KDE and Krita in the near future. Let’s keep in touch! (.w.)

短代码(一个马后炮)

没赶上报名截止日期,一直 not invited。就很难过。

E 的题目描述是这样的。

Description

tz学姐做题很忙,有一些简单的问题需要你帮忙解决:给定三个序列A,B,C和一个整数X, 现在需要找到三个数Ai,Bj,Ck,满足Ai+Bj+Ck = X.

Input

第1行三个整数 L, N, M;

第2行L个整数代表序列A

第3行M个整数代表序列B

第4行N个整数代表序列C

第5行1个整数S代表有S个X。

接下来的S行每行一个整数X

1<=L, N, M<=500, 1<=S<=1000. 所有整数均在32位整数范围内

Output

对于S个询问计算X对应的公式是否能被满足。 如能满足,输出 “YES”, 否则输出 “NO”。

Sample Input

1
2
3
4
5
6
7
8
3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

1
2
3
NO
YES
NO

我当时给出的代码是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int l,m,n;
cin>>l>>m>>n;
int a[l],b[m],c[n];
for(int&p:a)cin>>p;
for(int&p:b)cin>>p;
for(int&p:c)cin>>p;
sort(c,c+n);
cin>>n;
for(int p;cin>>p;){
for(int q:a)
for(int r:b)
if(binary_search(c,c+n,p-q-r)) {
cout<<"YES\n";
goto l;
}
cout<<"NO\n";
l:1;
}
}
//292

由于我不能提交,无法判断它是否超时了。查了一下网上的做法,是把 ab 加起来存到另一个数组里,然后对这个新的数组排序查找。

仔细分析一下就是:

我的方法,排序用了 O(n*log n),查找 O(n**2*log n)

另一个做法,排序 O(n**2*log n),查找 O(n*log n)

看上去好像正好抵消了没什么区别。问题在于查找是多次查找,我们希望每次查找的时间尽量短。

所以改过的代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int l,m,n,r=0;
cin>>l>>m>>n;
int a[l],b[m],c[n],S[l*m]; // GNU 扩展的变长数组
for(int&p:a)cin>>p;
// range-for 输入第二组数据,同时将输入的数据和第一组的每一个数字相累加,结果存到 `S` 里。
for(int&p:b) {
cin>>p;
for(int&q:a)S[r++]=p+q;
}
for(int&p:c)cin>>p;
sort(S,S+r);
cin>>n; // 丢弃个数信息,因为不需要
for(int p;cin>>p;){
for(int q:c)
if(binary_search(S,S+r,p-q)){
puts("YES");
goto l; // 直接跳到下次输入,不输出 NO
}
puts("NO");
l:1;
}
}
//311

排名表上最短是345。

但是有什么用呢。我又不能提交(以后一定要提前关注一下)。