This task is dedicated to establishing a definition of a //reverted// edit, as part of my GSoC 2020 project: {T248775}
I will later implement the chosen solution in MediaWiki's core.
There already a couple approaches to this problem out there, most notably the [[https://www.mediawiki.org/wiki/Extension:Echo|Echo extension]] and the [[https://pythonhosted.org/mwreverts/detection.html|mwreverts Python library]], both discussed below. Here I tried to compile the various requirements and ideas posted on Phabricator by people interested in this feature, most notably:
* {T164307}
* {T153570}
* {T152434}
* {T5640}
== Aspects
Important aspects we must consider when choosing the solution:
* Whether it will satisfy Echo's requirements, i.e. more or less match its current behavior for [[https://www.mediawiki.org/wiki/Help:Notifications/Types#Edit_reverts|revert notifications]]. It would be perfect if we could create a unified definition of a reverted edit, as it would significantly reduce confusion among users. We will also want to get rid of redundant revert detection code in Echo.
* Overall accuracy. We will never cover all cases, but we should try to cover a reasonable amount of them.
* Performance. A computationally expensive solution going through all diffs on a page is probably out of the question, we want to apply this tag right after the edit is saved.
== Possible solutions
Below I list some of the solutions that were proposed for the problem over the years.
=== Exact SHA1 matching
Entries in the `revision` table have the `rev_sha1` field, which, according to [[https://www.mediawiki.org/wiki/Manual:Revision_table#rev_sha1|documentation]], would be suitable for checking if the contents of all slots are equal in two revisions.
This is pretty much what the [[https://pythonhosted.org/mwreverts/detection.html|mwreverts Python library]] does for revert detection. The main difference is it does it completely off-wiki.
===== Pros
* That's perfect for exact reverts, i.e. reverting the page to an **exact** previous state.
* There probably won't be a lot of logic required to implement this.
* According to [[https://meta.wikimedia.org/wiki/Research:Revert#Identity_revert_via_checksum_with_history|this document]], about 94% of all reverts would be covered. Please note that this is based on research done in 2007 and can be //a bit// outdated. Still, I think it's safe to assume this method would have reasonable accuracy.
===== Cons
* Non-exact reverts (for example: user uses //undo// and makes some slight changes over it before saving) would not be handled.
* Reverting an intermediate change with automatic conflict resolution can create an entirely new SHA1, thanks to being a mix of two revisions. This wouldn't be handled.
* Other more complicated scenarios would not be handled, too.
* This does not match Echo's behavior at all.
Without an index on the `rev_sha1` field this would be very inefficient and have unpredictable performance. There are at least two solutions for that:
==== Add an index to the revision table
That would involve adding an additional index to the revision table, probably over `rev_page` and `rev_sha1` fields.
===== Pros
* Would allow for efficient checking for reverts on pages with very long history.
* Would offer better accuracy than the second method described below.
* The index may be useful for other possible features, such as looking up edits by their SHA1 through the API.
===== Cons
* Requires a schema change and an additional index. Any additional index slows down the DB on inserts/deletes slightly, so we have to have a good reason to introduce one.
==== Use radius search
This approach (also described [[https://meta.wikimedia.org/wiki/Research:Revert#Cutoffs_for_time_to_revert_and_edit_radius|here]]) would involve linearly going through SHA1s of n most recent edits or edits that were made at most x hours ago.
===== Pros
* The performance of this solution would be very predictable in most cases.
* We could make the search radius a configuration variable to let sysadmins decide on the balance between performance and accuracy.
===== Cons
* This wouldn't handle all cases. There are cases such as //deep reverts// that revert the page to a state it's been in even a few years ago. This is used rather rarely, though, and it is a very different rollback pattern.
* Another case this solution wouldn't handle are extreme cases of spam, where a vandal creates tens of revisions on the same page and we use radius search based on revision count. This is also quite rare, though, as this would be a very inefficient thing to do for a vandal.
=== Echo-like
In this approach we would try to more-or-less mimic current behavior of Echo when detecting reverted edits. I do not use Echo very often, so the following is mostly based on reading Echo's code, mainly [[https://phabricator.wikimedia.org/diffusion/ECHO/browse/master/includes/EchoHooks.php$537|this]] and [[https://phabricator.wikimedia.org/diffusion/ECHO/browse/master/includes/EchoHooks.php$1279|this]] hook. The current solution relies on some shady static variable, so it would be great if we could fix that along the way. I hope I understand the code correctly, but I may be wrong on the following pros and cons.
One possible improvement over the current implementation would be to support undoing multiple edits, as described in T153570.
===== Pros
* It handles well undos done through the //undo// link, even if the undoing user later applies some changes over it. I think.
* It handles the classic automatic rollback well, that is reverting one or multiple changes made by one user.
* Using this approach we would have a unified revert definition and could reuse the code in Echo easily. That would probably require a hook that would get triggered whenever an edit (or a group of edits) is reverted.
* It //should// handle reverting intermediate changes with automatic conflict resolution, as long as the reverting user uses the //undo// link.
* Very predictable performance.
===== Cons
* It does not handle manual reverts, that is reverting the page to a previous state not using //undo// or //rollback// links. That would mean reverts made with some gadgets would not be included.
=== Other
[[https://meta.wikimedia.org/wiki/Research:Revert#Full_and_partial_revert_detection_via_diffing|A method of identifying reverts by diffing was proposed]], but I don't think it would be suitable for this application given its high computational requirements.
=== Hybrid
It is possible to combine two approaches described above to cover more cases and achieve higher accuracy.
I would propose using the Echo-like method as the first stage and if it does not give us any results, proceed to a SHA1-based method. I propose to use radius search based on edit count, for example we would only check the last 15 revisions of page's history.
In this approach it may also be valuable to separate in code exact and non-exact reverts, as was suggested in T152434.
===== Pros
* It would handle the vast majority of cases out there, I think.
* This would be mostly consistent with what Echo does. Actually, by being an extension to Echo's behavior, it can be considered an improvement upon it. We would meet the requirement of creating a unified revert definition.
* This should also provide at least as good data as the [[https://pythonhosted.org/mwreverts/detection.html|mwreverts Python library]], if I understand correctly. Data science people may be pleased to hear that.
===== Cons
* This can significantly increase code complexity, so it may be wise to do some research into by how much would the accuracy actually improve before deciding on this.
== Conclusion
Personally, **I would go for the hybrid approach**, as it covers the majority of cases while being compatible with the needs of most groups interested in the feature. If we choose radius search, it would also not require any DB changes.
Any input on the topic is very welcome! :)
I also tag here my mentors: @kostajh and @Catrope