První série třicátého devátého ročníku KSP

Celý leták v PDF.

Dostává se k vám první číslo hlavní kategorie 39. ročníku KSP.

Letos (jako obvykle) se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále občas na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

• Termín série: neděle 25. října ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 39-1-1: Počet podposloupností KSP
• 39-1-2: Oboustranně nejbližší hnízdo
• 39-1-3: Vysílač
• 39-1-4: Sněhuláci
• 39-1-S: Hello, Rust!

39-1-1 Počet podposloupností KSP (10 bodů)

Kevin se po horkém létě konečně dostal k letáku zadání 1. série KSP. Když si ho tak ve stínu četl, všiml si, že se v něm často opakují písmenka K, S, P. To ho uvedlo do počítacího tranzu – kolikrát se v letáku vyskytuje řetězec KSP jako podposloupnost?

Pomozte Kevinovi s počítáním. Dostanete řetězec znaků. Vaším úkolem bude spočítat, kolikrát se slovo KSP vyskytuje v daném řetězci jako podposloupnost. KSP je podposloupnost řetězce, pokud se v něm nachází K, potom někdy později S a po něm někdy P. Například tedy KSP je podposloupností řetězce KASIOPEA.

Možná se vám bude hodit přečíst si naši základní kuchařku, zejména kapitolu Předpočítané mezivýsledky.

Formát vstupu: Na vstupu dostanete jeden řádek s řetězcem z velkých písmen anglické abecedy.

Formát výstupu: Vypište jedno číslo – počet, kolikrát se KSP vyskytuje v daném řetězci jako podposloupnost. Slibujeme, že výsledek se vejde do 64-bitového čísla, do 32-bitového už se ale vejít nemusí. Pokud programujete v Pythonu, nemusí vás to trápit, ale např. v Céčku budete potřebovat long long int.

KKSSKSP

7

Slovo KSP v daném řetězci najdeme jako podposloupnosti K_S___P, K__S__P, K____SP, _KS___P, _K_S__P, _K___SP, ____KSP.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

39-1-2 Oboustranně nejbližší hnízdo (11 bodů)

To se takhle Ríša potuloval v Bostonu, na svém dobrodružství za krocením orlů. U místního YMCA se zeptal svého spirituálního průvodce v podobě kamenného obličeje vytesaného do stěny, kde ve městě se nachází hnízda divokých orlů. No to je náhodička, že je to na každé křižovatce kromě té, na které zrovna stojí!

Ríša ale ví, že souboj s orlem bude lítý a únavný, proto chce šetřit své síly. A to jak při cestě k hnízdu, tak zpátky do YMCA. Proto by ho zajímalo, ke kterému orlímu hnízdu se má skrz spletitou síť bostonských jednosměrek vydat, aby mu cesta tam i zpět zabrala co nejméně času.

Ríša vás potřebuje. Nachází se u YMCA a neví kam dál. Pomozte mu najít hnízdo, pro které je součet délek nejkratší cesty tam a cesty zpátky nejmenší. Pokud je takových hnízd více, vyberte to na křižovatce s nejnižším číslem.

Může se vám bude hodit přečíst si naši kuchařku o grafech.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku jsou čísla N a M značící počet křižovatek a ulic.

Na dalších M řádcích jsou vždy dvě čísla u_i, v_i značící, že z křižovatky u_i do křižovatky v_i vede jednosměrná ulice. Křižovatky číslujeme od nuly.

Ríša stojí na křižovatce 0. Na všech křižovatkách kromě té jeho se nachází orlí hnízdo.

Formát výstupu: Na jediném řádku vypište dvě čísla: délku nejkratší možné výpravy z YMCA přes orlí hnízdo zpět do YMCA, a číslo orlího hnízda, které při ní navštívíme. Existuje-li více nejkratších výprav, zajímá nás ta s orlím hnízdem s co nejnižším číslem křižovatky. Slibujeme, že řešení existuje. Kromě toho o bostonské silniční síti nic neslibujeme, například neslibujeme, že se z každé křižovatky dá dostat na každou jinou.

5 8
0 1
0 2
1 2
2 4
3 4
4 0
4 1
4 3

3 2

Na křižovatku 2 se dá dostat cestou 0 →2 a z ní se zpátky do YMCA dá dostat cestou 2 →4 →0. Celkem tedy Ríša projde třemi ulicemi. Výprava kratší délky neexistuje a jediná další výprava délky tři je do orlího hnízda na křižovatce 4.

39-1-3 Vysílač (10 bodů)

Kocourkovský Starosta Petříček se rozhodl obyvatelům svého městečka zlepšit život. A co by lidem udělalo větší radost než rychlejší internet? Ono se to jednoduše zlepšuje, když počáteční množství vysílačů je nula. Protože však doteď žádný signál neměli, chtějí mít všichni vysílač co nejblíže k sobě.

Pomozte starostovi Petříčkovi umístit vysílač co nejférověji. Síla signálu pro jeden dům slábne s druhou mocninou euklidovské vzdálenosti od vysílače. Vymyslete, kam vysílač umístit, aby byl součet druhých mocnin euklidovských vzdáleností od vysílače ke každé budově co nejnižší.

Euklidovská vzdálenost je odvozena z Pythagorovy věty. Podívejte se na následující obrázek:

Na vstupu dostanete souřadnice N bodů v rovině reprezentujících domy Kocourkova. Vašim úkolem je zjistit, kam vysílač umístit. Důležité je také dokázat, že je vaše řešení správné.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

39-1-4 Sněhuláci (14 bodů)

Přichází podzim a Kevin moc dobře ví, co to znamená. Hbitě si nasazuje své pracovní kalhoty, gumáky a rukavice. Nikdo ho dnes nemůže zastavit. Je čas házet po kamarádech koule z bláta.

Jenže Sáře, Petrovi ani Honzovi se to z nějakého nepochopitelného důvodu nelíbí. Jenže jak zastavit Kevina, který si už na ně připravil nesčetně blátových koulí? Musí být vynalézaví. Proto Kevina přesvědčí, aby s municí udělal něco lepšího – aby ze svých koulí stavěl sněhuláky.

Pro ty nezasvěcené z vás: takový sněhulák se staví z jedné až tří různě velikých koulí. Kevinovi se nápad zprvu moc líbil, jenže pak si uvědomil, jak to jeho kamarádi mysleli. Rozhodl se proto na protest postavit sněhuláků co nejméně.

Pomozte Kevinovi vymyslet, do jakých skupin koule uspořádat, aby vzniklo sněhuláků co nejméně. Na vstupu dostanete seznam velikostí N Kevinových koulí – označme je k₁, …, k_N. Velikosti se mohou libovolně opakovat, avšak pro všechna i platí, že 1≤ k_i≤ 10N. Vymyslete algoritmus, který koule uspořádá do skupin po jedné až třech různě velkých koulích, aby bylo výsledných skupin co nejméně.

Poznámka: Jako vždy je hlavním kritériem hodnocení algoritmu jeho správnost. U této úlohy si doporučujeme opravdu důkladně rozmyslet, že vaše řešení funguje ve všech případech, i těch okrajových. Nezapomeňte důkaz správnosti zahrnout do řešení.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

39-1-S Hello, Rust! (15 bodů)

I letošním ročníkem vás bude provázet seriál. V každé sérii se objeví jeden díl, který bude obsahovat nějaké povídání a navíc úkoly. Za úkoly budete moci získávat body podobně jako za klasické úlohy série.

V letošním seriálu se zaměříme na Rust, programovací jazyk, který „umožňuje každému vytvářet spolehlivý a efektivní software“. Od verze 1.0 vydané v květnu 2015 se dočkal velké popularity – podle Stack Overflow Developer Survey 2026 Rust aktivně používá 18 % respondentů, 26 % respondentů jej chce používat a 67 % aktivních uživatelů jej chce používat nadále.

Pravděpodobně nejznámější vlastnost Rustu je jeho přístup k správě paměti. Díky tzv. borrow checkeru a pestré paletě abstrakcí nad pamětí ve standardní knihovně je možné v Rustu snadno psát kód, o kterém dokáže programátor i překladač dokázat, že neobsahuje žádné chyby spojené s paměťovou bezpečností. Borrow checker společně s dalšími featurami umožňuje Rustu velkou řadu možných chyb detekovat za překladu. Říká se, že pokud Rustový program jde přeložit, tak pravděpodobně seběhne.

Rust v sobě spojuje znaky vysokoúrovňových a nízkoúrovňových jazyků. Rustové programy jsou rychlé, srovnatelně s programy v C a C++. Rust navíc nepotřebuje žádné složité běhové prostředí a je možné z něj interagovat přímo s operačním systémem nebo hardware, což z něj dělá skvělou volbu pro programování mikrořadičů nebo operačních systémů. Jedná se tedy o dobrou alternativu k C nebo C++ v téměř všech jejich aplikacích. I přes to Rust obsahuje co nejvíce užitečných featur z vysokoúrovňových jazyků, jak to jen jde – například iterátory, asynchronní funkce, lambda funkce a generické funkce a struktury.

Cílem tohoto seriálu není vás naučit základy programování, akorát v Rustu. Budeme se zaměřovat na vlastnosti, které jsou pro Rust specifické. V tomto a následujícím díle seriálu prozkoumáme, jak se v Rustu pracuje s pamětí a ukazateli. Vysvětlíme si koncepty ownership a borrowing a ukážeme si, co dělá borrow checker. V následujících dílech si ukážeme, jak fungují algebraické datové typy, nebo jak psát v Rustu generický a paralelní kód.

Abychom vás hned na začátku neunudili k smrti, nebudeme začínat detailním rozborem základních syntaktických konstrukcí. Připravili jsme si pro vás proto krátký tahák, který najdete na konci tohoto dílu. Může se vám hodit při psaní řešení úkolů, k pochopení textu by potřeba být neměl. Pokud vám nebude jasné, jak nějaký kus kódu zapsat v Rustu, doporučujeme nahlédnout do oficiální příručky, případně do dokumentace standardní knihovny. Obě jsou podrobné a přehledné. Také se nás můžete zeptat v kanálu #seriál na našem Discordovém serveru.

Pro její pochopení tohoto seriálu budete potřebovat znát základy rozložení počítačové paměti – konkrétně rozdíl mezi haldou a zásobníkem volání. To (a mnoho více) se můžete dozvědět v naší kuchařce o paměti.

Poznejme svého nepřítele

Rust je paměťově bezpečný jazyk. Co to ale znamená?

Ve zkratce můžeme říci, že zabraňuje chybám, při kterých je k nějakému úseku paměti přistupováno, když k němu být přistupováno nemá. Takové chyby umí být velmi zrádné, protože se mohou projevit téměř jakkoliv. Jedna část kódu pak může přečíst nebo přepsat paměť myšlenou pro jinou část kódu, a najednou zjistíme, že jsme pánské boty přejmenovali na adresu zákazníka a naúčtovali mu částku rovnou jeho telefonnímu číslu.

Nejznámější chyby spojené s paměťovou bezpečností jsou tyto:

• Buffer overflow – Zapisujeme za konec (nebo před začátek) pole, čímž přepíšeme jiná data.
• Buffer over-read – Čteme za koncem (nebo před začátkem) pole, čímž přečteme špatná a možná nesmyslná data.
• Use after free – Použijeme ukazatel na místo v paměti, které už není platné – buď na uvolněnou alokaci na haldě nebo na proměnnou ve funkci, co už doběhla. Zajímavý speciální případ je, pokud použijeme ukazatel do nafukovacího pole, co se mezi tím zvětšilo, a tedy přesunulo.
• Double free – Jednu alokaci na haldě se pokusíme uvolnit podruhé. Jedná se vlastně o speciální případ use after free.
• Uninitialized read – Přečteme hodnotu proměnné nebo alokace na haldě, do které zatím nebyla přiřazena hodnota.
• Null pointer dereference – Pokusíme se přistoupit k paměti skrz ukazatel s hodnotou 0/null/nil. To je méně závažný problém než ty ostatní, protože v tomto případě je zaručeno, že program „bezpečně“ spadne. Výjimkou je C a C++, kde překladač může při optimalizaci předpokládat, že k použití null nedojde, tedy v opačném případě nemusí vygenerovaný kód dávat smysl.

Bitevní plán

A jak Rust těmto chybám zamezuje?

První dva případy není těžké odchytit – stačí při indexování pole zkontrolovat, jestli je index v rámci povolených mezí. To zní, jako by to mohlo být pomalé, nicméně se jedná jen o jeden podmíněný skok, který prediktor skoků v procesoru dokáže předpovědět s téměř 100% úspěšností, a navíc jej překladač umí odstranit, pokud při optimalizaci kódu dokáže, že index vždy v povolených mezích bude.

Řešení problémů s neinicializovanou pamětí také není až tak převratné. Pro proměnné Rust za překladu kontroluje, že v žádném možném průchodu funkcí není proměnná čtena před přiřazením, podobně jako to dělá C# nebo Java. A ostatním místům v paměti (prvkům polí, položkám struktur, …) musí být při vytvoření přiřazena hodnota.

Problémy s null také Rust vyřešil jednoduše – null totiž vůbec nemá. To se ale snáze řekne, než udělá – null se přeci jen při programování běžně používá. Rust tedy pro něj má náhradu, o které si řekneme více v nějakém dalším dílu.

Zbývá problém use after free (a příbuzný double free), tedy zajištění toho, že uvolnění místa v paměti nastane až po jeho posledním použití. Ten se ukazuje být ze všech nejzákeřnější. Klasické řešení je snažit se detekovat, že už alokace není potřeba, a automaticky ji uvolnit. K tomu se typicky používá tzv. garbage collector, který periodicky prochází paměť a dívá se na ukazatele, aby zjistil, jaká paměť je a není dosažitelná. To bohužel nevyhnutelně program zpomalí – samotný garbage collector potřebuje nějaký čas, nebo alespoň své vlákno, ostatní vlákna je nutné občas pozastavit, aby jim garbage collector nesahal pod ruce, a navíc si přeložený program musí dávat pozor na to, aby garbage collector všechny ukazatele zvládl najít. Rust proto volí opačný přístup – z kódu je pro každou alokaci jasné, kdy přesně bude uvolněna, a kontroluje se, že po uvolnění už do ní nemohou vést žádné ukazatele. K tomu slouží tzv. borrow checker, který za pomocí programátorem napsaných anotací kontroluje, že žádný ukazatel nepřežije místo v paměti, na které ukazuje.

Mnoho jazyků, které jsou sice běžně považovány za paměťově bezpečné, obsahují nějaké funkce, které paměťově bezpečné nejsou. Typickým příkladem jsou funkce, které umožní programu volat kód napsaný v jiném jazyce, typicky C nebo C++ (tzv. Foreign Function Interface, neboli FFI). Například v Pythonu můžete způsobit null pointer dereference v interpretu a tedy v něm vyvolat chybu segmentace (neboli SEGFAULT) spuštěním import ctypes; ctypes.string_at(0). Takovéto „nebezpečné“ funkce jsou ale v dokumentaci typicky jako nebezpečné jasně označené, s výčtem podmínek, za kterých je jejich použití bezpečné. Rust takové funkce obsahuje také, ale navíc vynucuje, že mohou být použité pouze v bloku unsafe { }. To má dvě výhody – zaprvé je pak nemožné nebezpečné funkce použít omylem, a zadruhé je snadné všechna jejich použití najít k následné kontrole. V Rustu se unsafe kód používá ke dvěma účelům: k interakci s kódem v jiném jazyce nebo s operačním systémem a k implementaci nových datových struktur a abstrakcí, které není možné poskládat z funkcí ve standardní knihovně. Při běžném programování typicky potřeba není a v tomto seriálu se s ním pravděpodobně vůbec nesetkáme.

Nakonec zmíníme jeden další problém spojený s pamětí, a to únik paměti neboli memory leak. Nastane, pokud program alokuje nějakou paměť a nikdy ji neuvolní, ačkoliv ji už nepotřebuje. Rust se únikům paměti snaží zabránit a je relativně snadné se jim vyhnout, nicméně je Rust nepovažuje za nebezpečné, a tedy je možné je vyvolat bez unsafe kódu.

Hello, Rust!

K práci budeme potřebovat Rustový překladač rustc a správce balíčku Cargo. Návod na instalaci obou najdete na stránkách Rustu. Také se vám bude hodit doplněk do editoru. Doporučuji doplňky založené na rust-analyzer, osobně jsem vyzkoušel jen ten pro Visual Studio Code.

Alternativně můžete místo lokální instalace použít oficiální online hřiště.

Založit nový program můžete pomocí příkazu cargo new název složky, případně v aktuální složce pomocí cargo init. Vytvořená složka bude obsahovat soubor Cargo.toml s metadaty o programu, jako je jeho název, verze a závislosti, automaticky udržovaný soubor Cargo.lock s přesnými verzemi všech použitých závislostí a složku src/ se zdrojovým kódem. Ze začátku v ní bude jediný soubor, vstupní bod main.rs, obsahující tradiční program „Hello, world!“

fn main() {
    println!("Hello, world!");
}

Program můžete sestavit a spustit příkazem cargo run. Ten vytvoří složku target/, ve které se bude ukládat přeložený program, společně se všemi mezikroky překladu. Kdybyste chtěli program přeložit s optimalizacemi pro distribuci, můžete použít příkaz cargo build --release, spustitelný soubor pak najdete na cestě target/release/jméno programu, na Windowsu navíc s příponou .exe.

Proměnné

Než se pustíme do popisu správy paměti v Rustu, tak si rychle ukážeme nějaká specifika Rustových proměnných. Začneme s jednoduchou booleovskou proměnnou:

fn main() {
    let is_earth_round = true;
}

Můžeme si všimnout, že proměnná nemá ve zdrojovém kódu uvedený žádný typ. To neznamená, že by žádný typ neměla – pokud bychom se do ní pokusili později přiřadit textový řetězec, tak by se program s chybou nepřeložil. Překladač Rustu totiž většinou umí typ proměnné odvodit z kontextu. Typ proměnné můžeme také deklarovat explicitně pomocí dvojtečky, například takto:

let is_earth_round: bool = true;

To je nutné udělat v případě, že typ proměnné překladač nedokáže jednoznačně odvodit z kódu, například pokud do ní přiřadíme prázdné pole. Pokud používáte výše doporučený doplněk do editoru, tak by měl automaticky odvozené typy naznačit šedým písmem. Rustový překladač typy neodvozuje jen z přiřazeného výrazu, ale ze všech použití dané proměnné. Například v tomto programu dokáže překladač odvodit, že radius má být 16-bitové znaménkové číslo (i16):

fn double_number(n: i16) -> i16 {
    n * 2 // Vrátíme 2 n.
}

fn main() {
    let radius = 6371;
    double_number(radius);
}

Rust má dvanáct celočíselných datových typů, šest znaménkových (i8, i16, i32, i64, i128 a isize) a šest bezznaménkových (u8, u16, u32, u64, u128 a usize). Všechny mají fixní velikost v bitech, až na isize a usize, které jsou na dané platformě vždy stejně velké jako ukazatel.

Proměnná vzniká v místě její deklarace a zaniká na konci bloku, v tomto případě na konci funkce. Do té doby ji můžeme libovolně číst a kopírovat. Pokud ji navíc chceme měnit, tak ji nejprve musíme označit klíčovým slovem mut:

fn factorial(n: u64) -> u64 {
    let mut result = 1;
    for i in 1..=n {
        result *= i;
    }
    result
}

Pro toto omezení neexistuje žádný technický důvod. Plyne z pozorování, že se v praxi do proměnných většinou jednou uloží nějaká spočítaná hodnota, která se poté do konce bloku už nemění. Proto Rust rozlišuje měnitelné (mutable, pomocí let mut) a neměnitelné (immutable, pomocí let) proměnné, aby čtenář kódu předem věděl, jestli má čekat, že se proměnná bude měnit. Podobně můžeme napsat for mut i in … nebo fn fun(mut n: u64).

Pokud chceme hodnotu proměnné změnit jenom párkrát, tak můžeme místo měnitelných proměnných využít zastiňování (shadowing). Pokud deklarujeme proměnnou se stejným jménem jako dřívější proměnnou, tak nová proměnná zastíní tu starou, další použití společného jména budou odkazovat na novou:

let n = 10;            // n je celé číslo.
let n = n as f64;      // Teď je reálné číslo.
let n = n.to_string(); // A teď je n řetězec.
println!("{n}");

Hlavní síla zastiňování ale spočívá v tom, že zastiňující proměnná nemusí mít stejný typ jako zastíněná. Rust svůj typový systém hojně využívá k reprezentaci různých vlastností a podmínek, takže je poměrně běžné, že během funkce jedna proměnná vystřídá několik typů.

Pamatujme na paměť

V této části si ukážeme, jak Rust zachází s pamětí. Začneme s číselnou proměnnou radius z předchozí části. Tady nás nečeká žádné velké překvapení – bude uložená přímo na zásobníku, jak znázorňuje tento diagram:

Číselné proměnné jsou jednoduché – mají konstantní, malou velikost, takže se snadno vejdou na zásobník a můžeme je bezstarostně kopírovat. V programech ale běžně pracujeme s hodnotami, co nemají konstantní velikost, například nafukovací pole a řetězce. U nich nám nezbývá, než je alokovat na haldě. K práci s haldou Rust používá tzv. smart pointery, podobně jako moderní C++. Jedná se o objekty/struktury, které mají na starosti nějaký dynamicky alokovaný kus paměti. Jeden z nich je String – dynamicky alokovaný řetězec. Vytvořit jej můžeme pomocí funkce String::from, která (v tomto použití) alokuje místo na haldě a zkopíruje tam konstantní řetězec (který má jiný typ):

let name = String::from("KSP");

Jedná se o nafukovací řetězec, můžeme jej tedy upravovat:

let mut name = String::from("KSP");
name.push('!');
println!("{name}"); // KSP!

Je lákavé říci, že proměnná name bude uložená na haldě. To ale není zcela pravda – samotná struktura String bude uložená na zásobníku, stejně jako každá jiná proměnná. Uvnitř této struktury bude uložený ukazatel na dynamicky alokovaný řetězec, který už na haldě bude. Navíc si struktura String pamatuje velikost řetězce a kapacitu alokované paměti. Situaci znázorňuje tento diagram:

Pro struktury je v Rustu možné nadefinovat destruktor – funkci, která bude zavolána automaticky, když proměnná zanikne. String a ostatní smart pointery mají destruktor, který uvolní spravovanou paměť. Veškerá paměť tím pádem bude uvolněna automaticky:

fn main() {
    let mut name =
        String::from("KSP"); // Alokujeme paměť.
    name.push('!');        // Alokace se zvětší.
}                          // Alokace se uvolní.

Destruktor je také zavolán, kdykoliv do proměnné přiřadíme novou hodnotu:

let mut name = String::from("Kevin");
    // Alokujeme paměť.
name = String::from("Sára");
    // Stará alokace se uvolní, vytvoří se nová.

Vlastnictví

Uvažujme následující kus kódu:

fn greet(to_greet: String) {
    println!("Hello, {to_greet}!");
}

fn main() {
    let name = String::from("KSP");
    greet(name);
}

Co přesně se na řádku greet(name) stane s proměnnou name? Mohli bychom si myslet, že se struktura String bit po bitu zkopíruje a tato kopie se předá funkci name, jak znázorňuje tento diagram:

Na řetězec na haldě by pak ukazovaly dva různé ukazatele. To ale nemůže fungovat. Na konci funkce greet proměnná to_greet zanikne, takže by v tu chvíli alokace řetězce na haldě byla uvolněna. Na konci main by pak zanikla proměnná name, a v tu chvíli by ta stejná alokace byla uvolněna podruhé, což víme, že za žádnou cenu nesmí nastat.

Narážíme tady na koncept, kterému se v Rustu říká vlastnictví, neboli ownership. Smart pointer vlastní svojí alokaci paměti – alokace vzniká a zaniká s ním. Abychom zabránili double free, je nezbytné, aby každá alokace měla právě jednoho vlastníka. Z toho plyne, že smart pointery alespoň přímočaře kopírovat nemůžeme.

Co se tedy v našem příkladu stane doopravdy? Jedna možnost by byla, že by Rust automaticky vytvořil kopii dynamicky alokované části String. Pro dlouhé řetězce by to ale byla pomalá operace, takže vývojáři Rustu nechtěli, aby v kódu nebyla vidět. Navíc existují typy, které snadno kopírovat nelze, například TcpStream představující otevřené internetové spojení.

Ve skutečnosti se proto String do funkce greet přesune – to znamená, že proměnná name přestane být platná a už ji nemůžeme dále používat. (Nicméně kdyby byla měnitelná, tak bychom do ní poté mohli přiřadit nový řetězec.) Tento kód se proto vůbec nepřeloží:

fn main() {
    let name = String::from("KSP");
    greet(name);
    println!("{name}"); // Chyba!
}

Obdobně funguje i přiřazení:

let a = String::from("KSP");
let b = a;
println!("{a}"); // Chyba!

Kdybychom řetězec chtěli před předáním funkci greet zkopírovat, tak samozřejmě můžeme. Spousta typů má metodu .clone(), která vrátí jejich kopii. Jedná se typicky o operaci s lineární časovou složitostí. Předchozí ukázku bychom tedy mohli opravit takto:

fn main() {
    let name = String::from("KSP");
    greet(name.clone());
    println!("{name}"); // V pořádku.
}

Typy v Rustu se tedy dělí na (implicitně) kopírovatelné (tzv. Copy typy) a nekopírovatelné. Předáním nekopírovatelného typu funkci proměnná zaniká, zatímco předání kopírovatelného typu proměnnou zachová. Mezi nekopírovatelné patří String, jak jsme už viděli, a obecně jakékoliv typy s nekonstantní velikostí. Mezi kopírovatelné patří celá čísla, čísla s plovoucí desetinnou čárkou, bool, pole konstantních délek jiných kopírovatelných typů, a obecně jakékoliv jiné malé hodnoty, například IpAddr.

Další chytré ukazatele

Rychle si představíme dva další smart pointery. První z nich je nafukovací pole Vec<T>, obdoba std::vector<T> z C++. Jedná se o generický typ (o nich více jindy), za T tedy můžeme dosadit libovolný typ, který budou mít všechny prvky. Prázdné pole můžeme vytvořit pomocí funkce Vec::new(), pro neprázdná pole můžeme použít makro (o nich také více jindy) vec![]. Výraz vec![a, b, c] vytvoří pole s prvky a, b, c a výraz vec![a; n] vytvoří pole s n kopiemi a. Použít jej můžeme například takto:

let mut vector: Vec<u32> = vec![1, 2, 3];
vector[0] += vector[1];
vector.push(42);
println!("{vector:?}"); // [3, 2, 3, 42]
println!("{len}", len = vector.len()); // 4

Vec<T> zevnitř vypadá stejně jako String – String je ve skutečnosti implementovaný pomocí Vec<u8>.

Ještě zmíníme Box<T>, nejjednodušší ze všech chytrých ukazatelů. Spravuje jednu hodnotu typu T umístěnou na haldě. Sám o sobě moc užitečný není, ledaže je typ T hodně velký.

Půjčování

Přesouvání argumentů do funkcí funguje dobře, pokud daná funkce onen argument potřebuje někam uložit (například push na Vec<T>), nebo jej přetvořit v něco jiného (například String::into_bytes, která umí String bez další alokace převést na Vec<u8>). Ve většině případů je ale nemožnost předaný argument dále používat nepříjemná a zbytečná. Mohlo by nás napadnout, že můžeme danou hodnotu funkci „půjčit“ – nejprve ji funkci předáme, a ona nám ji poté vrátí zpátky:

fn greet(to_greet: String) -> String {
    println!("Hello, {to_greet}!");
    to_greet // Vrátíme to_greet.
}

fn main() {
    let name = String::from("KSP");
    let name = greet(name);
    println!("{name}"); // V pořádku.
}

To by ale pro tak častou operaci bylo zbytečně složité. Místo toho můžeme argument funkci předat pomocí reference:

fn greet(to_greet: &String) {
    println!("Hello, {to_greet}!");
}

fn main() {
    let name = String::from("KSP");
    greet(&name);
    println!("{name}"); // V pořádku.
}

Reference není zevnitř nic jiného než obyčejný ukazatel. (Pokud znáte reference z C++, tak na ně raději zapomeňte – Rustové reference mají chováním mnohem blíže C++kovým ukazatelům než C++kovým referencím.) Referenci na proměnnou můžeme získat operátorem &, stejně jako v C nebo C++. Tu pak předáme funkci greet jako argument typu &String, neboli referenci na String.

Reference nejsou jen způsob předávání argumentů – jedná se o plnohodnotný typ, který můžeme například přiřadit do proměnné:

let number: u32 = 42;
let pointer: &u32 = &number;
let pointer_pointer: &&u32 = &pointer;

Pokud máme referenci na nějaký kopírovatelný typ, tak si můžeme jeho kopii pořídit pomocí operátoru *.

Hlavním rozdílem referencí oproti prostým ukazatelům je, že překladač kontroluje, že nemohou přežít proměnnou, na kterou ukazují, aby se zabránilo use after free. To je jeden z úkolů slavného borrow checkeru. Reference tedy vždy musí ukazovat na platnou hodnotu (a nic jako null pro ně tedy neexistuje). Například tento kód borrow checker zamítne, a tedy se nepřeloží:

let pointer: &u32;
{
    let number: u32 = 42;
    pointer = &number;
}
let number: u32 = *pointer; // Chyba!

Podotkneme, že bez posledního řádku by tento kód přeložit šel, protože se borrow checker ve skutečnosti zajímá jen o použití referencí – stačí tedy, když reference ukazuje na existující proměnnou do okamžiku jejího posledního použití.

Pokud máme referenci na nějakou hodnotu, tak z ní typicky můžeme získat i referenci na její logickou část, například na položku struktury nebo na prvek nafukovacího pole:

let vector: Vec<i32> = vec![75, 83, 80];
let vector_ref: &Vec<i32> = &vector;
let element_ref: &i32 = &vector_ref[0];

let range: Range<i32> = 0..39;
let range_ref: &Range<i32> = &range;
let start_ref: &i32 = &range_ref.start;

Podobně jako u proměnných se rozlišují měnitelné (&mut) a neměnitelné (&) reference. Skrz neměnitelnou referenci můžeme obecně hodnotu pouze číst, zatímco skrz měnitelnou jí můžeme upravit nebo úplně přepsat. Například:

fn make_shouty(string: &mut String) {
    // Můžeme použít push, což řetězec změní:
    string.push('!');
}

fn make_hippo(string: &mut String) {
    // Můžeme také řetězec zcela nahradit:
    *string = String::from("Hroch");
}

fn main() {
    let mut string = String::from("KSP");
    make_shouty(&mut string);
    make_hippo(&mut string);
}

Měnitelnou referenci pochopitelně můžeme vytvořit pouze na měnitelnou proměnnou. Uložená zato může být i v neměnitelé proměnné – měnitelnost proměnné s referencí určuje jen to, jestli je možné referenci nahradit za jinou.

Z měnitelné reference můžeme udělat neměnitelnou, ale ne naopak.

Měnit, či neměnit

Uvažujme následující kus kódu:

let mut vector = vec![1, 2, 3];
let first = &vector[0];
vector = vec![75, 83, 80];
println!("{first}"); // Funguje tohle?

Vytvoříme pole vector a vytvoříme referenci first na jeho první prvek. Poté do proměnné vector přiřadíme nové pole, což uvolní staré pole. Ukazatel first tím pádem bude ukazovat do uvolněné paměti, a jeho následné použití bylo use after free, což víme, že nesmíme dopustit.

To nás vede k dalšímu pravidlu ohledně referencí: Nesmíme do proměnné přiřadit novou hodnotu, pokud na nějakou její logickou část vede reference. Naše ukázka toto pravidlo porušuje, proto se nepřeloží.

Přiřazení do proměnné ale není jediný způsob, kterým můžeme hodnotu nahradit nebo změnit – měnitelné reference mohou způsobit stejný problém:

fn add_element(vector: &mut Vec<i32>) {
    vector.push(4936528);
}

fn main() {
    let mut vector = vec![1, 2, 3];
    let first = &vector[0];
    add_element(&mut vector);
    println!("{first}"); // Chyba!
}

Tentokrát místo přiřazení do pole jen přidáme další prvek. Přidání prvku do nafukovacího pole nicméně může způsobit jeho realokaci, což opět rozbije ukazatel first. (Navíc překladač při kontrole main neví, že add_element pole nenahradí celé.)

To nás vede k druhému, příbuznému pravidlu: Na jedno místo v paměti smí v jednu chvíli vést buď libovolný počet neměnitelných referencí, nebo jedna měnitelná. (Nebo žádná, samozřejmě.)

Kontrolování těchto dvou pravidel je další z úkolů borrow checkeru.

Protože měnitelná reference smí v jednu chvíli existovat jen jedna, jsou měnitelné reference přirozeně nekopírovatelné typy, zatímco neměnitelné reference jsou kopírovatelné typy.

Přepůjčování

Tak, jak jsme je popsali, by měnitelné reference nebyly příliš užitečné. To, že jsou nekopírovatelné, by znamenalo, že bychom je po předání funkci už nemohli dále používat. Například tento kód by podle našich dosavadních znalostí neměl jít přeložit, neboť by první volání make_shouty referenci urgent_str spotřebovalo:

fn make_shouty(string: &mut String) {
    string.push('!');
}

fn make_very_shouty(urgent_str: &mut String) {
    make_shouty(urgent_str);
    make_shouty(urgent_str);
    make_shouty(urgent_str);
}

Funkce používající měnitelné reference by tedy prakticky nebylo možné skládat. To by bylo velmi nepříjemné, proto Rust jakési omezené „kopírování“ měnitelných referencí podporuje skrze koncept, kterému se říká reborrowing. Z jedné měnitelné reference (tady urgent_str) můžeme odvodit novou (tady string), ale jen za předpokladu, že starou referenci nebudeme používat, dokud nová nepřestane existovat. Předchozí ukázka kódu tedy v pořádku je – během volání make_shouty sice na stejný řetězec ukazují dvě měnitelné reference, urgent_str a string, ale urgent_str se v tu chvíli vůbec nepoužívá. Používat se znovu začne až potom, co na konci make_shouty reference string zanikne.

„Přepůjčená“ reference nemusí být přesná kopie původní reference – z reference na hodnotu můžeme odvodit referenci na její logickou část. Například:

let mut vector = vec![1, 2, 3];
let vector_ref = &mut vector;
let element_ref = &mut vector_ref[0];
*element_ref = 42;
*vector_ref = vec![75, 83, 80];

Vytvoříme měnitelnou referenci na vektor, poté z ní vytvoříme referenci na jeho prvek. Referenci na prvek poté použijeme, a když s ní jsme hotoví, tak můžeme začít opět používat původní referenci. (Tady využíváme toho, že borrow checker referenci přestane sledovat v místě posledního použití.) Kdybychom poslední dva řádky prohodili, tak by se kód nepřeložil, neboť by pak musely existovat dvě aktivní reference souběžně.

Pokud chcete referenci přepůjčit jedna ku jedné, tak toho můžete docílit kombinací operátorů &mut *hodnota. Při volání funkce se ale přepůjčuje automaticky, takže to typicky není potřeba dělat manuálně.

Vlastní typy

Závěrem si ukážeme, jak si můžete v Rustu založit vlastní strukturu. Deklaruje se pomocí klíčového slova struct, je potřeba uvést její jméno a jména i typy jejích položek:

struct Task {
    code: String,
    points: u32,
    solved: bool,
}

Pokud chceme vytvořit její instanci, tak stačí uvést její jméno a hodnotu pro každou položku:

let task: Task = Task {
    code: String::from("39-1-S"),
    points: 15,
    solved: false,
};
println!("{}", task.code); // 39-1-S

Před definici struktury můžeme přidat #[derive(Debug)], což nám umožní vypsat obsah struktury ve formátu pro ladění pomocí formátovacího specifikátoru :?:

#[derive(Debug)]
struct Series {
    year: u32,
    number: u16,
}

fn main() {
    let series = Series { year: 39, number: 1 };
    println!("{series:?}");
        // Series { year: 39, number: 1 }
}

Pokud jsou všechny položky kopírovatelné, tak můžeme obdobně použít #[derive(Clone, Copy)], abychom strukturu označili jako kopírovatelnou.

Poté, co jsme strukturu deklarovali, jí můžeme přidat metody pomocí bloku impl. Do něj napíšeme hlavičky a těla funkcí, které se stanou metodami. Musíme ale uvést, jakým způsobem se funkci předá samotná struktura, na které byla metoda zavolána. To uděláme pomocí prvního, speciálního argumentu self:

impl Task {
    // Statická metoda:
    fn new(code: String, points: u32) -> Task {
        Task { code, points, solved: false }
    }

    // Metoda, které stačí neměnitelná reference:
    fn points_obtained(&self) -> u32 {
        if self.solved { self.points }
        else { 0 }
    }

    // Metoda vyžadující měnitelnou referenci:
    fn set_solved(&mut self, solved: bool) {
        self.solved = solved;
    }

    // Metoda, do které se struktura přesune:
    // Po jejím zavolání proměnná zaniká.
    fn into_code(self) -> String {
        self.code
    }
}

Použít je můžeme takto:

let code = String::from("39-1-S");
let mut task = Task::new(code, 15);
task.set_solved(true);
let points = task.points_obtained();
let code = task.into_code();
    // task už dále použít nemůžeme.

Odevzdávání úkolů

V tomto díle jsme si pro vás připravili tři nezávislé úkoly. Do odevzdávátka nahrajte archiv ve formátu ZIP obsahující řešení všech úkolů, které chcete řešit. Zdrojový kód odevzdejte jako soubor .rs nebo jako složku s Cargo projektem.

Úkol 1 – Zobecněná Fibonacciho čísla [3b]

Napište funkci fn fibonacci(n: u64, a: i64, b: i64) -> i64, která spočítá číslo dané následující rekurencí:

Časovou složitost optimalizovat nemusíte. Možnost přetečení můžete ignorovat.

Připravili jsme pro vás sadu testů. Stačí je přidat na konec vašeho zdrojového kódu, spustit je poté můžete příkazem cargo test. Stáhnout si je můžete zde.

Úkol 2 – Diagram Vec<String> [5b]

Uvažujme proměnnou vector vytvořenou následujícím kódem:

let string = String::from("KSP");
let mut vector = Vec::new();
vector.push(string.clone());
vector.push(string);

Nakreslete diagram, jak vypadá na konci funkce, podobně jako diagram pro String výše. Mělo by z něj být vidět, kolik úseků haldy bude alokováno a co bude uložené v každém z nich a na zásobníku. Odevzdejte jej buď jako PDF soubor, nebo jako obrázek ve formátu PNG, JPG, WEBP, apod.

Úkol 3 – Disjoint-Find-Union [7b]

Naprogramujte datovou strukturu Disjoint-Find-Union. Její popis a implementaci v Pascalu můžete najít v naší kuchařce o minimálních kostrách.

Mělo by ji být možné používat takto:

// Založíme graf bez hran s 3 vrcholy 0, 1, 2.
let mut dfu = DisjointFindUnion::new(3);
// Zkontrolujeme, jestli 0 a 1 jsou spojené.
println!("{}", dfu.find(0, 1)); // false
// Přidáme hranu (0, 2).
dfu.union(0, 2);
// Přidáme hranu (1, 2).
dfu.union(1, 2);
// Zkontrolujeme, jestli 0 a 1 jsou spojené.
println!("{}", dfu.find(0, 1)); // true

Co se stane, pokud bude nějaký parametr mimo povolený rozsah, řešit nemusíte.

I tady jsme si pro vás připravili sadu testů. Stáhnout si je můžete zde.

Benjamin Swart

Syntaktický tahák

// Funkce s argumentem, bez návratové hodnoty:
fn printing(value: String) {
    // Psaní do konzole pomocí formátovacího řetězce:
    println!("The value is {value}");
    // Alternativně pro výraz:
    println!("Uppercase: {}", value.to_uppercase());
    // Nebo jinak:
    println!("Length: {len}", len = value.len());
    // Ve formátu pro ladění:
    println!("For debugging: {value:?}");

    // Ladicí formát má většina typů,
    // zato základní mají jen některé.
    // Použité proměnné se předají referencí.
}

// Funkce s argumenty a návratovou hodnotou:
fn returning(a: u32, b: u32) -> u32 {
    if a == b {
        // Předčasný návrat z funkce:
        return 42;
    }

    // Vrácení hodnoty na konci funkce:
    (a + b * 2) * b // Bez středníku!
}

fn variables() {
    // Proměnná s odvozeným typem:
    let i = 4936528;
    // Proměnná s explicitním typem:
    let j: i32 = 4936528;
    // Měnitelná proměnná:
    let mut k = 6371;
    k *= 2; // Totéž jako k = k * 2.

    // Číselná konstanta s explicitním typem:
    let m = 4936528u64;
    // Převod mezi číselnými typy:
    let n = m as i32;

    // Založení pole s danými prvky:
    let mut bytes: Vec<u8> = vec![75, 83, 80];
    // Založení pole vyplněné kopiemi prvku:
    let one_hundered_zeroes = vec![0; 100];

    // Přístup do pole:
    bytes[1] = 18;
    // Index musí být typu usize.

    // Vytvoření neměnitelné reference:
    let reference = &i;
    // Přečtení reference na kopírovatelný typ:
    let value = *reference;

    // Vytvoření měnitelné reference:
    let mut_reference = &mut k;
    // Přiřazení do reference:
    *mut_reference = 42;
}

fn conditions(a: u32, b: u32) {
    // Podmíněný kód:
    if a < b {
        println!("a < b");
    } else if a > b {
        println!("a > b");
    } else {
        println!("a = b");
    }

    // Použití podmínky pro určení hodnoty:
    let abs_diff = if a > b {
        a - b // Bez středníku!
    } else {
        b - a // Bez středníku!
    };
}

fn loops() {
    // Smyčka přes zprava otevřený interval:
    for i in 0..10 { println!("{i}"); }
    // Smyčka přes uzavřený interval:
    for i in 0..=10 { println!("{i}"); }
    // Smyčka přes neměnitelné reference do pole:
    for i in &vec![1, 2, 3] { println!("{i}"); }
    // Smyčka přes měnitelné reference do pole:
    for i in &mut vec![1, 2, 3] { println!("{i}"); }
    // Smyčka přes přesunuté prvky pole (pole uvolní):
    for i in vec![1, 2, 3] { println!("{i}"); }

    let mut i = 42;
    // Smyčka s vlastní podmínkou:
    while i > 0 {
        i /= 2;
    }

    let mut i = 4936528;
    // Nekonečná smyčka:
    loop {
        if i == 1 {
            // Ukončení smyčky:
            break;
        }
        if i % 2 != 0 {
            i = 3 * i + 1;
            // Ukončení jedné iterace smyčky:
            continue;
        }
        i = i / 2;
    }

    // Označení smyčky:
    'outer: loop {
        loop {
            // Ukončení konkrétní smyčky:
            break 'outer;
        }
    }

    let result: i32 = loop {
        // Ukončení nekonečné smyčky s hodnotou:
        break 42;
    };
}

// Automatická implementace ladicího formátování:
#[derive(Debug)]
// Deklarace struktury:
struct Structure {
    a: i32,
    b: Vec<bool>,
}

// Viz „Vlastní typy“ pro ukázku deklarace metod.

fn structures() {
    let b = vec![true, false];
    // Vytvoření struktury:
    let structure = Structure {
        a: 10,
    // Nastavení položky na stejnojmennou proměnnou:
        b,
    };
}

// Vstupní bod programu:
fn main() {}