we convene that lines are "paragraphs", i.e. separated by line feed or other characters or character combinations; the differ should identify these, and/or the user should be able to identify these by option; it's understood that we don't speak of displayed screen "lines"
regular comparison:
text A - text B
compare line A1 to line B1 and so on
if beyond line Bx there are y non corresponding lines, compare line Ax+1 with every line Bx+y+1+z within a reasonable scope, or perhaps shift to B after some tries and try to find lines in A, corresponding to lines in B
i.e. I did not really delve into regular comparison
problem 1 above, by option, do this additional comparison, interwoven with regular comparison:
compare Ax with Bx, but also with compound of (Bx and Bx+1), the control-n or control-n plus control-r in B being considered null, a space, a space and a special character and a space, or any other "replacement" string the user will make the differ consider "equal", just as in regular comparison presets for text IN line (cf. the various and otherwise very satisfying possibilities for in-line comparison in BC)
if by this "joined lines" comparison, Bx and Bx+1 are considered equal to Ax,
then next don't compare Ax+1 with Bx+2, but with Bx+2, and, according to our optional rule here, to Bx+3, etc.
do respectively for comparing Bx to Ax and (Ax plus Ax+1); the option would be simpler to program if the user had to decide on which "side" the possible "1 line split up into 2 lines" could occur, but it's evident it would be more "elegant" for the differ to detect such splits on both sides (I do not treat the additional problem brought up by 3-way comparisons)
maintain additional buffers in order to store these intermediate results and do again regular compare from these
problem 2 above, by option
first, the underlying idea:
do the regular comparison
identify (i.e. put into an additional buffer A2) all lines in A for which the differ doesn't find corresponding lines in B by the regular comparison (which could include comparison according to problem 1 and other options)
compare these lines in A2, one by one, with every line in an additional buffer B2 which will contain every line of B for which the differ has NOT identified, by the above "rich regular" comparison, a corresponding line in A
if A2x is present in B2, replace the line "not found" in original buffer B (and which corresponds to the corresponding line in original buffer A), by a line "REL" for "relocated" or such (and mark the line in A2 als "resolved")
idem for the "not found" line in A, which corresponds to the corresponding line in B (and which contains the respective line of B2): "REL" here in A's otherwise empty line which does not correspond to B's line (but which corresponds, as seen, to some OTHER line within A)
(it's evident that you will need ID numbers for every original line in A and B, and which follows them into the additional buffers, since line numbers in the intermediate buffers will not correspond to original line numbers in A and B)
remaining "unsolved" buffer A2 lines will correspond to those lines in A which do not corresponding lines in B, and ditto for orphan lines in B2, without corresponding lines in A, for lines in B
it's understood that the differ, by the above script, will consider every FIRST occurrence of a relocated line as the relocation, possible copies of that line further being considered as additional copies; in most real-life scenarios (expecially textbooks and programming with shuffling around of text passages or code bits), we all could live with such an assumption (see below)
and now for the real-life solution of problem 2 since identifying displaced lines is devoid of sense, in 99 p.c. of possible scenarios (you will notice that in my post above, I did NOT list "line 1/2/3" but "para 1/2/3"):
in fact, authors/programmers do not displace single lines, but compounds of lines, i.e. paragraph suites, or if you prefer, "real" paragraphs, comprising perhaps 3 or 15 "paragraphs" = technically, lines, and even some blank lines for grouping, within
this means, in order to resolve problem 2, in a realistic i.e. useful way, we must allow the user to identify "real paragraphs", e.g. by 2 blank lines (whilst 1 blank line would be identified as a regular blank line within such a "compound paragraph"), or a ^n^r (in this scenario, the author or programmer would "hold together" "real" paragraphs by just typing ^n and even, for blank lines, ^n^n, within them, but "close" them with a ^n^r); similar means of differenciating "real" paragraphs from "just new lines within a paragraph" would be conceivable
then, complication of my explanation above, this "identify replaced paras" routine would of course not do the above-explained work for lines, but first of all, it would unite all lines in A and in B, respectively, into "real para" compounds, and it would then do the above-described work for those paras instead (cf. 1 blank line in A vs. 20 blank lines in B, at the same position, and which do not cause any problem to traditional differs)
the only remaining weakness in this (albeit quite satisfactory yet) real-life solution would be the non-identification of relocated "real" paras in which additionally you will have done some minor changes: in such cases, the above routine would only identify two non-correspondences, one in A, one in B, and without telling you, neither for the A para nor for the B one (which, remember, has been relocated), that in fact, there is a corresponding piece of code or of text elsewhere, just slightly changed/amended
therefore, we spice up the above routine by a sub-routine which checks, for these paras in A2, all paras in B2 for "slight variation", similarly to a pic differ, and which, according to the preferences of the user, would allow for some changed or added or replaced or deleted single lines if the replaced code/text otherwise was clearly "identifiable" as a variant/amendment*
and finally, it's not really practical (i.e. especially in the case of not-100-p.c.-tally) that you would necessarily have just "REL" lines, on both sides, for these single occurrences at that given location in A resp. in B: by option, it should be possible to replicate the "text/code over there, HERE", instead, i.e. replaced "real paras" would be cloned in the corresponding B display, for their A occurence, even though they have been relocated in B, and another clone would be shown in A, at the corresponding position for their new position in B; these replications would be in a pre-determined color of course
*= the same could apply, by option, to NOT-relocated, but slightly changed text/code: here, too, an optional sub-routine could identify the whole "real para", and then display it in whole, on both sides, in a predefined color, instead of the usual display which would only display the non-changed lines within those text or code blocks, without their context; an even more useful variant of this would be a dedicated command/toggle "show full blocks on both sides" if the mouse cursor is, on either side, within a line identified as "not identical"
in a deluxe version, you then could even implement a similar routine which both would show indications to other (identical or near-) duplicates, and show ALL those, i.e. all occurences of them, of one or the other or both sides, alternatively to the regular display
it's all about the multiplication of intermediate / supporting buffers and concordance tables in arrays for lines and blocks
EDIT:
you also could identify the length of a block, and the fact if it's (to be considered and to be treated as) a block or not, by "following" the first relocated line of a possible block and then check, "over there", how much "meat" it comprises, i.e. you identify the first relocated occurence of its first line, then compare "backwards", i.e. identify if the lines following there (new location in B) are identical / similar to what follows the original line in A (but not on the location in B corresponding to that location in A); this would be much more elegant, especially if you allow for possible new content interwoven into that relocated block, i.e. do NOT stop the comparison after just some (new) lines in the B flavour of the block, but continue to search for content identical / similar to what follows in A, even (reasonably) further down there in B
at this time, e.g. in BC, "identical vs. non-identical" is either-or, i.e. you can define SPECIFIC inconsistencies to be regarded as "equal"; it's evident that you could introduce a "fuzzy" approach ("similar in spite of up to x differences of this kind AND/OR y differences of that other kind"), alternatively and in general, or specifically for within (possible) blocks
.
