P2SH-P2WPKH - has always segwit UTXOs? I've been reading a lot of docs on BTC transaction structure, and find it really confusing when it comes to SegWit story.
So, the very first thing is, if I've P2SH-P2WPKH address, does it mean that all outputs to this address (UTXOs) are by definition segwit UTXOs ?
In the docs (https://bitcoincore.org/en/segwit_wallet_dev/) it says:

Signature Generation and Verification for P2SH-P2WPKH
For spending of non-segwit UTXO, the signature generation algorithm is  unchanged.
For spending of P2SH-P2WPKH:

The scriptSig MUST ONLY contain a push of the redeemScript

...

So, either all UTXOs for P2SH-P2WPKH address are segwit ones, or they are SegWit if SegWit transaction was made to this address (which does little sense actually for me, as then arises chicken-egg problem).
Why they wrote this &quot;For spending of non-segwit UTXO, the signature generation algorithm is  unchanged&quot; part, what case it covers? If you've P2SH-P2WPKH address but you are taking some foreign UTXOs to spend(that were directed not to your address)?
Another not clear part are scripts for P2SH-P2WPKH address.
So here is my example address:
3MxYPuvEcKDdaEG1xoGyddqir6C4b66MJi
And here is transaction that was made to it:
https://blockchain.info/rawtx/6c2806587d5cdb3f0363e43f60b4a84baf37b3012fbde02f108f4eb1bdcede42
Based on it pubKeyScript of output is a914de523116b281c96ff1e204ea2ff435b75d48f0de87 which translates to:
OP_HASH160 de523116b281c96ff1e204ea2ff435b75d48f0de OP_EQUAL

So, de523116b281c96ff1e204ea2ff435b75d48f0de is hash160 of redeem script.
The only redeem script that matches this hash I've found is following:
0 389f26d8d616cb96df1cfd6d9989248a30b933b9

Which is witness v0 program script(0 sha160sha256(pubkey), so it means I've to create SegWit transactions, right?
I tried making P2SH ones and it says that I've non-nominal pushes in the redeem script, that's cause of &quot;0&quot; push there I believe.
I feel that doing something wrong in this part, and as a result signing either wrong thing or in a wrong way...
Very appreciate any explanations.
if I've P2SH-P2WPKH address, does it mean that all outputs to this
  address (UTXOs) are by definition segwit UTXOs ?


Yes, Bitcoin sent to a P2SH-P2WPKH address will produce a segwit UTXO.


  Why they wrote this "For spending of non-segwit UTXO, the signature
  generation algorithm is unchanged" part, what case it covers? If
  you've P2SH-P2WPKH address but you are taking some foreign UTXOs to
  spend(that were directed not to your address)?


I think you're right, it sounds like it's just saying if you want to send to a segwit address, you don't need to sign a non-segwit input any differently than before.

Spending P2SH(P2WPKH)

Here is a good reference example: BIP 141: P2SH(P2WPKH). In order to spend Bitcoin sent to your address 3MxYPuvEcKDdaEG1xoGyddqir6C4b66MJi, you have to provide the following:

witness:      &lt;signature&gt; &lt;pubkey&gt;
scriptSig:    &lt;0 &lt;20-byte-key-hash&gt;&gt;
              (0x160014{389f26d8d616cb96df1cfd6d9989248a30b933b9})


Perhaps you are forgetting the push ops 0x16 and/or 0x14 in scriptSig?