Currently, func_index_compare_with_key compares only functional key
of tuple. But when we will implement pagination, we will need to
find a tuple with a certain primary key. This commit fixes
the problem and introduces key_compare_and_skip_parts helper.

NO_CHANGELOG=internal
NO_DOC=internal

Part of #7633

To implement pagination, we need an entity which describes iterator
position in index with serialization and deserialization methods.
Extracted cmp_def is most appropriate, so the patch introduces
serialization and deserialization methods to pack key as position in index.

NO_CHANGELOG=internal
NO_DOC=internal

Closes #7635

The patch introduces new virtual method and extends existing one
for the needs of pagination. New functional is not implemented, stubs only.

Index virtual method create_iterator is extended with new argument pos,
If it is passed, iterator points to the first tuple after position,
described by this argument (or error is returned if index does not
support pagination). If pos is NULL, method has the same
behavior as before this patch.

Function index_create_iterator_after now calls create_iterator method
and index_create_iterator calls the same method but passes NULL as pos
argument.

Also the patch introduces a new virtual method of iterator -
iterator_position. It returnes position (extracted cmp_def without
MP_ARRAY header) of last fetched tuple, or NULL if no tuples were
fetched.

NO_TEST=no behavior changes
NO_CHANGELOG=internal
NO_DOC=internal

Part of #7633

NO_DOC=bugfix
NO_CHANGELOG=bugfix for unreleased bug

The idea is borrowed from [1]: hide and save prompt, user's input and
cursor position before writing to stdout/stderr and return everything
back afterwards.

Not every stdout/stderr write is handled this way: only tarantool's
logger (when it writes to stderr) and tarantool's print() Lua function
performs the prompt hide/show actions. For example,
`io.stdout:write(<...>)` Lua call or `write(STDOUT_FILENO, <...>)` C
call may mix readline's prompt with actual output. However the logger
and print() is likely enough for the vast majority of usages.

The readline's interactive search state (usually invoked by Ctrl+R) is
not covered by this patch. Sadly, I didn't find a way to properly save
and restore readline's output in this case.

Implementation details
----------------------

Several words about the allocation strategy. On the first glance it may
look worthful to pre-allocate a buffer to store prompt and user's input
data and reallocate it on demand. However rl_set_prompt() already
performs free() plus malloc() at each call[^1], so avoid doing malloc()
on our side would not change the picture much. Moreover, this code
interacts with a human, which is on many orders of magnitude slower that
a machine and will not notice a difference. So I decided to keep the
code simpler.

[^1]: Verified on readline 8.1 sources. However it worth to note that
      rl_replace_line() keeps the buffer and performs realloc() on
      demand.

The code is organized to make say and print modules calling some
callbacks without knowledge about its origin and dependency on the
console module (or whatever else module would implement this interaction
with readline). The downside here is that console needs to know all
places to set the callbacks. OTOH, it offers explicit list of such
callbacks in one place and, at whole, keep the relevant code together.

We can redefine the print() function from every place in the code, but I
prefer to make it as explicit as possible, so added the new internal
print.lua module.

We could redefine _G.print on demand instead of setting callbacks for a
function assigned to _G.print once. The downside here is that if a user
save/capture the old _G.print value, it'll use the raw print() directly
instead of our replacement. Current implementation seems to be more
safe.

Alternatives considered
-----------------------

I guess we can clear readline's prompt and user input manually and don't
let readline know that something was changed (and restore the
prompt/user input afterwards). It would save allocations and string
copying, but likely would lean on readline internals too much and repeat
some of its functionality. I considered this option as unstable and
declined.

We can redefine behavior for all writes to stdout and stderr. There are
different ways to do so:

1. Redefine libc's write() with our own implementation, which will call
   the original libc's write()[^2]. It is defined as a weak symbol in
   libc (at least in glibc), so there is no problem to do so.
2. Use pipe(), dup() and dup2() to execute our own code at
   STDOUT_FILENO, STDERR_FILENO writes.

[^2]: There is a good article about pitfalls on this road: [2]. It is
      about LD_PRELOAD, but I guess everything is very similar with
      wrapping libc's function from an executable.

In my opinion, those options are dangerous, because they implicitly
change behavior of a lot of code, which unlikely expects something of
this kind. The second option (use pipe()) adds more user space/kernel
space context switches, more copying and also would add possible
implicit fiber yield at any `write(STD*_FILENO, <...>)` call -- unlikely
all user's code is ready for that.

Fixes #7169

[1]: https://metacpan.org/dist/AnyEvent-ReadLine-Gnu/source/Gnu.pm
[2]: https://tbrindus.ca/correct-ld-preload-hooking-libc/

NO_DOC=this patch prevents mixing of output streams on a terminal and it
       is what a user actually expects; no reason to describe how bad
       would be his/her life without it

A basic (and pretty useless) example:

```lua
local it = require('test.luatest_helpers.interactive_tarantool')

local child = it.new()

child:execute_command('6 * 7')
local res = child:read_response()
t.assert_equals(res, 42)

child:close()
```

The module also contains `:read_line()`, `:assert_line()` helpers for
testing output directly: for example, when we need to catch a print()
from a background fiber. It provides has constants related to terminal's
control sequences.

A real usage can be seen in a next commit.

Part of #7169

NO_DOC=no user visible changes
NO_TEST=not applicable, it is a testing helper
NO_CHANGELOG=no user visible changes

Those callbacks will be set from the console module (which integrates
readline into tarantool), so the print() output won't mix with readline
prompting.

Part of #7169

NO_DOC=no user visible changes, it is internal API
NO_TEST=will be tested in a next commit together with the console
        callbacks itself
NO_CHANGELOG=no user visible changes

Those callbacks will be set from the console module (which integrates
readline into tarantool), so the stderr output won't mix with readline
prompting.

Part of #7169

NO_DOC=no user visible changes, it is internal API
NO_TEST=will be tested in a next commit together with the console
        callbacks itself
NO_CHANGELOG=no user visible changes

Caught the following error with UB sanitizer after trying to use the
31-st vclock component in one of the tests:

NO_WRAP
```
[040] +/opt/actions-runner/_work/tarantool/tarantool/src/lib/vclock/vclock.c:133:21: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
[040] +SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /opt/actions-runner/_work/tarantool/tarantool/src/lib/vclock/vclock.c:133:21 in
[040] Test "unit/vclock.test", conf: "None"
[040] 	failed, rerunning ...
[040] unit/vclock.test                                                [ fail ]
```
NO_WRAP

Let's fix this in all the affected places.

NO_DOC=refactoring
NO_TEST=already tested by unit/vclock.cc: test_minmax_ignore0()
NO_CHANGELOG=refactoring

We hold the following invariant in MVCC: the story at the top of the
history chain is present in index.

If a story is subject to be deleted from index and there is an older story
in the history chain, the older story starts to be at the top of the
history chain and is not present in index, which violates our invariant:
explicitly check for this case when evaluating whether a story can be
garbage collected and add an assertion to check the invariant above is not
violated.

Rollbacked stories need to be handled in a special way: they are
present at the end of some history chains and completely unlinked from
others (which also implies they are not present in the corresponding
indexes).

`memtx_tx_story_full_unlink` is called in two contexts: space deletion, in
which we delete all stories, and garbage collection step — the former case
can break the invariant described above, while the latter must preserve it,
hence add two different functions for the corresponding contexts.

Closes #7490

NO_CHANGELOG=<internal bugfix not user observable>
NO_DOC=<bugfix>

When we rollback a transaction statement, we relink its read trackers
to a newer story in the history chain, if present (6c990a7b), but we do not
handle the case when there is no newer story.

If there is an older story in the history chain, we can relink the
rollbacked story's reader to it, but if the rollbacked story is the
only one left, we need to retain it, because it stores the reader list
needed for conflict resolution — such stories are distinguished by the
rollbacked flag, and there can be no more than one such story located
strictly at the end of a given history chain (which means a story can be
fully unlinked from some indexes and present at the end of others).

There are several nuances we need to account for:

Firstly, such rollbacked stories must be impossible to read from an index:
this is ensured by `memtx_tx_story_is_visible`.

Secondly, rollbacked transactions need to be treated as prepared with
stories that have `add_psn == del_psn`, so that they are correctly deleted
during garbage collection.

After this logical change we have the following partially ordered set over
tuple stories:
———————————————————————————————————————————————————————> serialization time
|- - - - - - - -|— — — — — -|— — — — — |— — — — — — -|— — — — — — — -
| No more than  | Committed | Prepared | In-progress | One dirty
| one rollbacked|           |          |             | story in index
| story         |           |          |             |
|- - - - - - - -|— — — — — -| — — — — —|— — — — — — -|— — — — — — — —

Closes #7343

NO_DOC=bugfix

`struct memtx_story` has a `space` field, which is basically used
to identify that a tuple is unlinked from the history chain in
`memtx_tx_index_invisible_count_slow` (though this can be determined by its
presence in the index) and is used to get the space's index in
`memtx_tx_story_link_top` (though it can be  retrieved from the older
story's link field): remove this redundant field.

Needed for #7343

NO_CHANGELOG=<refactoring>
NO_DOC=<refactoring>
NO_TEST=<refactoring>

When a space is deleted, all transactions need to be aborted and all their
stories need to be removed immediately out of order: currently we
artificially rollback statements — instead call this statement
removal to logically distinguish it from rollback. It differs in the sense
that the whole space's tuple history is teared down instead — no more
transaction managing is going to be done as opposed to rollback of an
individual transaction.

Needed for #7343

NO_CHANGELOG=refactoring
NO_DOC=refactoring
NO_TEST=refactoring

Follow `memtx_tx_history_{add, prepare}_{insert, delete}` pattern: split
code responsible for rollbacking addition and deletion of a story into
separate functions.

Needed for #7343

NO_CHANGELOG=refactoring
NO_DOC=refactoring
NO_TEST=refactorin

When a statement gets rollbacked, we need to remove delete statements
attached to the story it adds by relinking them and making them delete an
older story in the history chain: refactor this loop out into a separate
function.

Needed for #7343

NO_CHANGELOG=refactoring
NO_DOC=refactoring
NO_TEST=refactoring

If a statement becomes prepared, the story it adds must be 'sunk' to
the level of prepared stories: refactor this loop into a
separate function.

Needed for #7343

NO_CHANGELOG=refactoring
NO_DOC=refactoring
NO_TEST=refactoring

Change error from "ER_QUORUM_WAIT: fiber is cancelled" to
FiberIsCancelled for consistency with other places that check for fiber
cancellation.
Same of "ER_QUORUM_WAIT: timed out". Change it to TimedOut.

While I'm at it, make box_wait_quorum tolerate spurious wake-ups.

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

Linearizability is a property of operations when operation performed on
any node sees all the operations performed earlier on any other node of
the cluster.

More strictly speaking, it's a property demanding that if a response
for some write request arrived earlier than some read request was made,
this read request must see the results of that (or any earlier) write
request.

This patch introduces a new transaction isolation level: 'linearizable'.
When the option is set, box.begin() is stalled until the node receives the
latest data from at least one member of the quorum. This is needed to
make sure that the node sees all the writes committed on a quorum.
The transaction is served only after the node sees the relevant data,
thus implementing linearizable semantics.

The node working on a linearizable request uses its' relays vclock sync
mechanism in order to know the fresh vclock of remote nodes.

Closes #6707

@TarantoolBot document
Title: New transaction isolation level - linearizable

There is a new transaction isolation level - linearizable.
You may call `box.begin` with `txn_isolation = 'linearizable'`, but you
can't set the default transaction isolation level to 'linearizable'.

Linearizable transactions may only perform requests to synchronous,
local or temporary memtx spaces (vinyl engine support will be added
later).

Starting a linearizable transaction requires
`box.cfg.memtx_use_mvcc_engine` to be on.

Note: starting a linearizable transaction requires that the node is the
replication **source** for at least N - Q + 1 remote replicas. Here `N` is
the count of registered nodes in the cluster and `Q` is
`replication_synchro_quorum` value (the same as
`box.info.synchro.quorum`). This is the implementation limitation. For
example, you may start linearizable transactions on any node of a
cluster in full-mesh topology, but you can't perform linearizable
transactions on anonymous replicas, because noone replicates **from**
them.

When a transcaction is linearizable it sees the latest changes performed
on the quorum of nodes in the cluster. For example, if you use
linearizable transactions to read data on a replica, such a transaction
will never read stale data: all the committed writes performed on the
master will be seen by the transaction.

Making a transaction linearizable requires some waiting until the node
receives all the committed data. In case the node can't contact enough
remote peers to determine which data is committed an error is returned.

Waiting for committed data may time out: if the data isn't received
during the timeout specified by `timeout` option of `box.begin()`, an
error is returned.

When called with `{txn_isolation = 'linearizable'}`, `box.begin()`
yields until the instance receives enough data from remote peers to be
sure that the transaction is linearizable.

Currently replication acks deliver vclock the replica has reached to the
master. But there is no guarantee on how fresh that vclock is: by the
time the ack arrives, real replica vclock might be much greater.

In some applications relay can't rely on arbitrarily old ack vclock. It
needs an upper bound on vclock which could be reached by the replica at
some specific point in time.

In order to achieve this, introduce vclock syncs. A vclock sync is a
monotonically growing heartbeat identifier, unique for a live
master-replica connection. This identifier may now be appended to
heartbeats coming from the master. Once receiving a heartbeat with some
non-zero vclock sync value, replica starts responding with the same
vclock sync value in all its acks.

Here's how it can be used: for example, in multi-master configuration,
one master wants to wait until it receives all the data, that was present
on a remote master at some point in time. In order to do so, the first
master issues a vclock sync request. Once it receives an ack with the
same vclock sync it has sent, it knows for sure that the remote master's
vclock was not greater than the one received in the ack.

This may be used to implement linearizable reads.

Prerequisite #6707

NO_TEST=tested in next commit
NO_CHANGELOG=internal change

@TarantoolBot document
Title: Binary protocol: new key - IPROTO_VCLOCK_SYNC
Binary protocol receives a new key:
IPROTO_VCLOCK_SYNC = 0x5a
This key holds a MP_UINT value and is used only by replication
heartbeats. A master sends the monotonically growing vclock sync together
with some of its heartbeats, and replica replies with the greatest vclock
sync it has seen yet in its ACKs.

Reuse check_param_table() funciton in box begin instead of some custom
parameter checking code.
As one of the side effects, unknown options are now declined by
`box.begin{}`, which becomes more and more important with new options
introduction.

In-scope-of #6707

NO_DOC=refactoring
NO_CHANGELOG=refactoring

To match space_is_temporary.

In-scope-of #6707

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

GROUP_LOCAL and GROUP_DEFAULT were defined in vclock.h, which isn't the
right place for them, so move them somewhere more appropriate.

In-scope-of #6707

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

Make the function arguments const, and, while I'm at it, fix function
formatting.

In-scope-of #6707

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

relay->tx.is_raft_enabled flag is used to track when relay is ready to
accept raft pushes. That is, when tx and relay thread endpoints are paired.

Actually, there is a designated callback, which is run right at the
moment of pairing: pair_cb of cbus_pair().

Let's use it and its counterpart, unpair_cb of cbus_unpair() to notify
tx when relay is ready to accept raft pushes.

This approach is notably simpler and allows to reuse the notification
for other systems which might want to access relay pipe.

In-scope of #6707

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

As a counterpart to vclock_min_ignore0

NO_DOC=internal change
NO_CHANGELOG=internal change

All of the current cbus_call() invocations pass TIMEOUT_INFINITY as a
timeout and don't provide any free_cb.

Since commit bd6fb06a ("core: allow
spurious wakeups in cbus_call") cbus_call() with TIMEOUT_INFINITY can't
be interrupted at all, so  there's no point to pass free_cb for it.

Let's simplify cbus_call() usage by removing the last two arguments,
free_cb and timeout.

These arguments will be present in a new function, cbus_call_timeout.

Simplify all current cbus_call() usages which have TIMEOUT_INFINITY.
Remove free_cb, where present, and stop allocating call messages
dynamically, since static allocation works just fine now.

NO_DOC=refactoring
NO_CHANGELOG=refactoring

The commit bd6fb06a ("core: allow
spurious wakeups in cbus_call") mistakenly removed the msg->caller
cleanup after a spurious wakeup or a timeout. Fix that.

NO_DOC=internal change
NO_CHANGELOG=internal change

Feedback daemon is reconfiguread as many times as number of options
changed during single box.cfg call which is suboptimal. Add proper support
for modules which configure all its options in a single call.

Part of https://github.com/tarantool/tarantool-ee/issues/200

NO_DOC=refactoring
NO_TEST=refactoring
NO_CHANGELOG=refactoring

Some luatest framework tests use Lua `assert`s, which are incomprehensible
when failed (the only information provided is 'assertion failed!'),
making debugging difficult: replace them with luatest `assert`s and their
context-specific varieties.

NO_CHANGELOG=<code health>
NO_DOC=<code health>

If an update operation tried to insert a new key into a map or an
array which was created by a previous update operation, then the
process would fail an assertion.

That was because the first operation was stored as a bar update.
The second operation tried to branch it assuming that the entire
bar update's JSON path must exist, but it wasn't so for the newly
created part of the path.

The solution is to fallback to branching earlier than the entire
bar path ends, if can see that the next part of the path can't be
found.

Closes #7705

NO_DOC=bugfix

TREE (HASH) index implements `random` method: if the space is empty from
the transaction's perspective, which means we have to return nothing, add
gap tracking of whole range (full scan
tracking), since this result is equivalent to `index:select{}`, otherwise
repeatedly call `random` and clarify result, until we get a non-empty one.
We do not care about performance here, since all operations in context of
transaction management currently have O(number of dirty tuples)
complexity.

Closes #7670

NO_DOC=bugfix

Since `key_def_merge` sets the merged key definition's unique part count
equal to the new part count, the extra assignment in case the index is not
unique is redundant: remove it.

NO_CHANGELOG=<refactoring>
NO_DOC=<refactoring>
NO_TEST=<refactoring>

If TREE index `get` result is empty, the key part count is incorrectly
compared to the tree's `cmp_def->part_count`, though it should be compared
with `cmp_def->unique_part_count`. But we can actually assume that by the
time we get to the index's `get` method the part count is equal to the
unique part count (partial keys are rejected and `get` is not
supported for non-unique indexes): change check to correct assertion.

Closes #7685

NO_DOC=<bugfix>

Replaced assertions, that no one started new elections/promoted while
acquiring limbo, with checks that raft term and limbo term didn't
change. In case they did - don't write DEMOTE/PROMOTE and just release
limbo, because it's already owned/will soon be by someone else.

Closes #7086

NO_DOC=Bugfix

@TarantoolBot document
Title: Document encoding parameters in http client

New option "params" passed to HTTP request allows a user to add query
parameters into URI. When option "params" contains a Lua table with
key-value pairs these parameters encoded to a string and passed as an
URL path in GET/HEAD/DELETE methods and as a HTTP body with POST method.
In a latter case error will be raised when body is not empty.

```
> uri = require("uri")
> httpc = require("httpc")
> params = { key1 = 'value1', key2 = uri.values('value1', 'value2') }
> r = http.client.get("http://httpbin.org/get", { params = params })
> r.url
---
- http://httpbin.org/get?key1=value1&key2=value1&key2=value2
...

```

Key and values could be a Lua number, string, boolean, anything that has
a `__serialize` or `__tostring` metamethod. It is possible to pass
datetime, decimal and number64 values.

Limitations:

- order of keys with values in a result string is not deterministic
- percent encoding is not supported at the moment

Closes #6832

@TarantoolBot document
Title: Document encoding HTTP parameters to a query string

New method uri.values() allows a user to represent multivalue
parameter's.

Setting multivalue parameter with `uri.parse()` and `uri.format()`:

```
> params = {q1 = uri.values("v1", "v2")}}
> uri.format({host = 'brnkv.ru', params = params})
---
- http://x.html?q1=v1&q1=v2
...

> uri.parse({"/tmp/unix.sock", params = params)
---
- host: unix/
  service: /tmp/unix.sock
  unix: /tmp/unix.sock
  params:
    q1:
    - v1
    - v2
...

```

Key and values could be a Lua number, string, boolean, anything that has
a `__serialize` or `__tostring` metamethod. It is possible to pass
`datetime`, `decimal` and `number64` values too.

NOTE: Order of keys with values in a result string is not deterministic.

Needed for #6832

Patch introduces two internal functions: `uri.params()` and
`uri.encode_kv()`.

NO_CHANGELOG=internal
NO_DOC=internal

Needed for #6832

NO_CHANGELOG=internal
NO_DOC=internal
NO_TEST=internal

NO_CHANGELOG=internal
NO_DOC=internal
NO_TEST=internal

Currently, it is possible to create a constraint with a name that does
not match the rules for identifiers. Fix this by validating them by
identifier_check.

Closes #7201

NO_DOC=bugfix
NO_CHANGELOG=minor bug