refactor(sign): move legacy signs to extmarks

Problem:  The legacy signlist data structures and associated functions are
          redundant since the introduction of extmark signs.
Solution: Store signs defined through the legacy commands in a hashmap, placed
          signs in the extmark tree. Replace signlist associated functions.

Usage of the legacy sign commands should yield no change in behavior with the
exception of:
  - "orphaned signs" are now always removed when the line it is placed on is
    deleted. This used to depend on the value of 'signcolumn'.
  - It is no longer possible to place multiple signs with the same identifier
    in a single group on multiple lines. This will now move the sign instead.

Moreover, both signs placed through the legacy sign commands and through
|nvim_buf_set_extmark()|:
  - Will show up in both |sign-place| and |nvim_buf_get_extmarks()|.
  - Are displayed by increasing sign identifier, left to right.
    Extmark signs used to be ordered decreasingly as opposed to legacy signs.

7 files changed, 21 insertions, 29 deletions

diff --git a/runtime/doc/api.txt b/runtime/doc/api.txt
index 6970479a78..1b11d8571a 100644
--- a/runtime/doc/api.txt
+++ b/runtime/doc/api.txt
@@ -2566,8 +2566,8 @@ nvim_buf_get_extmark_by_id({buffer}, {ns_id}, {id}, {opts})
 
                                                      *nvim_buf_get_extmarks()*
 nvim_buf_get_extmarks({buffer}, {ns_id}, {start}, {end}, {*opts})
-    Gets |extmarks| in "traversal order" from a |charwise| region defined by
-    buffer positions (inclusive, 0-indexed |api-indexing|).
+    Gets |extmarks| (including |signs|) in "traversal order" from a |charwise|
+    region defined by buffer positions (inclusive, 0-indexed |api-indexing|).
 
     Region can be given as (row,col) tuples, or valid extmark ids (whose
     positions define the bounds). 0 and -1 are understood as (0,0) and (-1,-1)
diff --git a/runtime/doc/news.txt b/runtime/doc/news.txt
index ae97772b66..818f0e5a57 100644
--- a/runtime/doc/news.txt
+++ b/runtime/doc/news.txt
@@ -80,6 +80,14 @@ The following changes may require adaptations in user config or plugins.
   the option is set (e.g. using |:set| or |nvim_set_option_value()|) without a
   scope, which means they now behave the same way as string options.
 
+• Signs placed through the legacy |sign-commands| are now stored and displayed
+  as |extmarks| internally. Along with the following changes:
+  • A sign placed twice in the same group with the same identifier will be moved.
+  • Legacy signs are always deleted along with the line it is placed on.
+  • Legacy and extmark signs will show up in both |:sign-place-list| and |nvim_buf_get_extmarks()|.
+  • Legacy and extmark signs are displayed and listed with the same priority:
+      line number -> priority -> sign id -> recently placed
+
 ==============================================================================
 NEW FEATURES                                                    *news-features*
 
diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt
index 07326c8c13..f47093782c 100644
--- a/runtime/doc/options.txt
+++ b/runtime/doc/options.txt
@@ -5624,12 +5624,6 @@ A jump table for the options with a short description can be found at |Q_op|.
 	   "number"	display signs in the 'number' column. If the number
 			column is not present, then behaves like "auto".
 
-	Note regarding "orphaned signs": with signcolumn numbers higher than
-	1, deleting lines will also remove the associated signs automatically,
-	in contrast to the default Vim behavior of keeping and grouping them.
-	This is done in order for the signcolumn appearance not appear weird
-	during line deletion.
-
 			*'smartcase'* *'scs'* *'nosmartcase'* *'noscs'*
 'smartcase' 'scs'	boolean	(default off)
 			global
diff --git a/runtime/doc/sign.txt b/runtime/doc/sign.txt
index 8ecfadce17..733b0fe212 100644
--- a/runtime/doc/sign.txt
+++ b/runtime/doc/sign.txt
@@ -53,11 +53,10 @@ If 'cursorline' is enabled, then the CursorLineSign highlight group is used
 Each placed sign is identified by a number called the sign identifier. This
 identifier is used to jump to the sign or to remove the sign. The identifier
 is assigned when placing the sign using the |:sign-place| command or the
-|sign_place()| function. Each sign identifier should be a unique number. If
-multiple placed signs use the same identifier, then jumping to or removing a
-sign becomes unpredictable. To avoid overlapping identifiers, sign groups can
-be used. The |sign_place()| function can be called with a zero sign identifier
-to allocate the next available identifier.
+|sign_place()| function. Each sign identifier should be a unique number.
+Placing the same identifier twice will move the previously placed sign. The
+|sign_place()| function can be called with a zero sign identifier to allocate
+the next available identifier.
 
 							*sign-group*
 Each placed sign can be assigned to either the global group or a named group.
@@ -77,9 +76,8 @@ When two signs with the same priority are present, and one has an icon or text
 in the signcolumn while the other has line highlighting, then both are
 displayed.
 
-When the line on which the sign is placed is deleted, the sign is moved to the
-next line (or the last line of the buffer, if there is no next line).  When
-the delete is undone the sign does not move back.
+When the line on which the sign is placed is deleted, the sign is removed along
+with it.
 
 ==============================================================================
 2. Commands					*sign-commands* *:sig* *:sign*
@@ -177,11 +175,8 @@ See |sign_place()| for the equivalent Vim script function.
 		space is ignored.
 
 		The sign is remembered under {id}, this can be used for
-		further manipulation.  {id} must be a number.
-		It's up to the user to make sure the {id} is used only once in
-		each file (if it's used several times unplacing will also have
-		to be done several times and making changes may not work as
-		expected).
+		further manipulation.  {id} must be a number.  Placing the
+		same {id} multiple times will move the sign.
 
 		The following optional sign attributes can be specified before
 		"file=":
diff --git a/runtime/doc/vim_diff.txt b/runtime/doc/vim_diff.txt
index 05d7e5feb9..fb23535c76 100644
--- a/runtime/doc/vim_diff.txt
+++ b/runtime/doc/vim_diff.txt
@@ -340,6 +340,7 @@ Shell:
 
 Signs:
   Signs are removed if the associated line is deleted.
+  Signs placed twice with the same identifier in the same group are moved.
 
 Startup:
   |-e| and |-es| invoke the same "improved Ex mode" as -E and -Es.
diff --git a/runtime/lua/vim/_meta/api.lua b/runtime/lua/vim/_meta/api.lua
index 2142a429a2..70a8b0aec2 100644
--- a/runtime/lua/vim/_meta/api.lua
+++ b/runtime/lua/vim/_meta/api.lua
@@ -317,8 +317,8 @@ function vim.api.nvim_buf_get_commands(buffer, opts) end
 --- @return integer[]
 function vim.api.nvim_buf_get_extmark_by_id(buffer, ns_id, id, opts) end
 
---- Gets `extmarks` in "traversal order" from a `charwise` region defined by
---- buffer positions (inclusive, 0-indexed `api-indexing`).
+--- Gets `extmarks` (including `signs`) in "traversal order" from a `charwise`
+--- region defined by buffer positions (inclusive, 0-indexed `api-indexing`).
 --- Region can be given as (row,col) tuples, or valid extmark ids (whose
 --- positions define the bounds). 0 and -1 are understood as (0,0) and (-1,-1)
 --- respectively, thus the following are equivalent:
diff --git a/runtime/lua/vim/_meta/options.lua b/runtime/lua/vim/_meta/options.lua
index 19ae786177..6d693ca036 100644
--- a/runtime/lua/vim/_meta/options.lua
+++ b/runtime/lua/vim/_meta/options.lua
@@ -5923,12 +5923,6 @@ vim.go.siso = vim.go.sidescrolloff
 ---    "number"	display signs in the 'number' column. If the number
 --- 		column is not present, then behaves like "auto".
 ---
---- Note regarding "orphaned signs": with signcolumn numbers higher than
---- 1, deleting lines will also remove the associated signs automatically,
---- in contrast to the default Vim behavior of keeping and grouping them.
---- This is done in order for the signcolumn appearance not appear weird
---- during line deletion.
----
 --- @type string
 vim.o.signcolumn = "auto"
 vim.o.scl = vim.o.signcolumn