Vigade otsimine

Mida teha, kui esitad võistlusel lahenduse ja server annab vastuseks "vale vastus" või "programmi täitmine ebaõnnestus (nullist erinev veakood)"? Esimese asjana võib muidugi kontrollida, ega koodis mingit ilmset viga ei ole. Aga pärast seda? Paljud võistlejad jäävad suhteliselt kiiresti hätta ja ei oska teha muud, kui viimases hädas suvalisi "kahtlaseid" asju muuta. Kogemus näitab, et sarnaseid probleeme on isegi kogenud võistlejatel.

Vigade otsimine on tegelikult protsess, mida saab teha väga süstemaatiliselt ja mis on suhteliselt kergesti õpitav. Kindlasti on see protsess palju lihtsam ja kiirem lahenduste välja mõtlemisest. Olukorrad, kus programmis vea leidmine võtab rohkem kui pool tundi, peaksid olema erandlikud.

Esimene reegel: ükskõik mis töökeskonda (Emacs, vi, PyCharm, VS Code) kasutades tuleks olla tuttav selle tähtsamate funktsionaalsustega. Kindlasti on kohustuslik teada:

Need ei peaks olema asjad, mida alles võistluse jooksul uurima hakata!

Tõsiselt soovituslik on ka käsurea mingil määral tundmine. Käsurea tundmine tekitab ka IDE-s samade asjade tegemisest parema arusaamise (vastupidine ei kehti). Sealhulgas on soovituslik ka käsureal debuggeri kasutamise oskus: graafiline debugger on üks nendest asjadest, mis võistluskeskkondades katki kipub olema.

Enamus kaasaegsetes IDE-des on mingisugune käsurida sisse ehitatud:

Vali ülaribalt Terminal → New Terminal (võib väiksemal ekraanil olla "..." taga).

Avanenud käsurida näeb välja nii:

Vali paremalt alt nurgast märgitud ikoon.

Avanenud käsurida näeb välja nii:

M-x ansi-term

Võib kasutada ka eraldiseisvat terminalprogrammi. Linuxi tarnetes on pea alati mingisugune terminal sisse ehitatud (otsi menüüst "Terminal"). Windowsis on kaks terminali: vanem Command Prompt ja uuem PowerShell. Nendest võib kasutada emba-kumba, aga süntaks ja paljud käsud on erinevad.

Käsurea kiirkursus

Teeme läbi lihtsa harjutuse: programmi käsurealt kompileerimise ja käivitamise.

Käsureal on alati mingi failisüsteemi kaust lahti. Selles mõttes sarnaneb käsurida natuke operatsioonisüsteemi sisseehitatud failihalduriga.

Et teada saada milline, käivita käsk pwd (cd). Siin ja igal pool järgnevas on sulgudes olev käsk Command Prompti oma. Kaustas olevate failide loetelu trükib ekraanile ls (dir).

Selleks, et teisse kausta navigeerida, saab kasutada käsku cd. Näiteks kausta code navigeerimiseks kasutage cd code. Käsk cd .. liigub ühe kausta võrra üles. Neid käske kasutades liigume kausta, kus programm asub.

Selleks, et ühest failist koosnevat programmi program.cpp kompileerida, kasutame käsku

g++ program.cpp -o program

Selle tulemusena tekib kausta uus fail program (Windowsis program.exe), mille käivitamiseks tuleb teha ./program (Command Promptis program.exe või .\program).

Kompilaatorile g++ saab erinevaid täiendavaid argumente ette anda. Näiteks käsk

g++ program.cpp -O2 -Wall -g -o program

lülitab sisse optimeerimise (-O2), näitab kõiki hoiatusi (-Wall) ja lisab kompileeritud faili debugimisinfo (-g).

Pythonis kirjutatud programmi käivitamine käib nii:

python program.py

Sõltuvalt installeeritud interpretaatorist võib olla vaja kirjutada python asemel python3, pypy või pypy3.

Muid kasulikke käske:

1. Sisendi-väljundi suunamine

Enamus võistlustel, sealhulgas EIO-l, antakse sisend nn standardsisendist ja nõutakse, et väljund trükitaks standardväljundisse. Teisisõnu, sisend on see, "mida klaviatuurilt sisestatakse" ja väljund see, "mida ekraanile trükitakse". See aga ei tähenda, et seda ka ise testides peaks käsitsi sisse tippima: see on väga tüütu ja veaohtlik. Natuke parem variant on selle copy-pastemine, kuid ka see on näiteks suurte sisenditega testimise korral täiesti kasutu.

On ka hoopis lihtsam moodus: salvestada sisend faili ja käivitada programm nii, et faili sisu oleks "justkui klaviatuurilt sisestatud". Oletame näiteks, et programmi nimi on program ja sisendfaili nimi input.txt. Siis käib see nii:

./program < input.txt

program.exe < input.txt

Get-Content input.txt | ./program

Samamoodi saab väljundi suunata eraldi faili output.txt. Neid kahte lähenemist saab isegi kombineerida:

./program > output.txt
./program < input.txt > output.txt

program.exe > output.txt
program.exe < input.txt > output.txt

./program > output.txt
Get-Content input.txt | ./program > output.txt

Pythonis kirjutatud programmide puhul näevad need käsud välja analoogilised, täpsemalt:

python program.py < input.txt
python program.py > output.txt
python program.py < input.txt > output.txt

python program.py < input.txt
python program.py > output.txt
python program.py < input.txt > output.txt

Get-Content input.txt | python program.py 
program.py > output.txt
Get-Content input.txt | python program.py > output.txt

Sõltuvalt installeeritud interpretaatorist võib olla vaja python asemel kirjutada python3, pypy, pypy3 vms.

On ka teine populaarne meetod: programmis endas failist lugemine ja faili kirjutamine, aga ainult juhul, kui programmi käivitatakse lokaalselt.

CMS kompileerib kõiki programme lipuga -DEVAL. See tähendab, et kui C++ programmi tekstis kirjutada

#ifdef EVAL
    // siia kirjuta midagi
#endif

siis selle ploki sisu CMSis käivitatakse, aga mujal mitte, kui just ise sedasama lippu ei kasuta. Võib ka vastupidi: CMSis lippu (näiteks) -DLOCAL ei kasutata, aga oma arvutis testides võib seda teha.

See tähendab, et võime programmi lisada koodi, mis suunab faili ümber standardsisendisse nii, et see kood CMSis ei jookse:

#include <cstdio>

using namespace std;

// ...

int main () {
#ifndef EVAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  // programm ise
}

Nüüd viitab lokaalsel käivitamisel cin failile input.txt ja cout failile output.txt, CMSis aga kasutatakse standardsisendit ja standardväljundit nagu ikka. Mitte kõik platvormid ei kasuta lippu -DEVAL (levinud on ka näiteks hoopis -DONLINE_JUDGE), seega vast isegi kindlam on kontrollida lokaalse lipu puudumist:

#include <cstdio>

using namespace std;

// ...

int main () {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  // programm ise
}

Selle toimimiseks tuleb kompileerimise käsureal kasutada lippu -DLOCAL, näiteks g++ a.cpp -DLOCAL -o a.

2. fsanitize

See osa on relevantne ainult C++ kasutajatele.

Pythonis ja paljudes teistes keeltes annab programm vigade korral enam-vähem mõistlikke veateateid.

arr = [0, 1, 2]
print(arr[4])

Traceback (most recent call last):
  File "/test/broken.py", line 2, in <module>
    print(arr[4])
          ~~~^^^
IndexError: list index out of range

C++ on teistsugune. Vead, nagu massiivi piiride ületamine, ei pruugi mingisugust veateadet anda. Näiteks ülaloleva programmi C++ ekvivalent:

#include <iostream>
#include <vector>

int main () {
  std::vector<int> arr = {0, 1, 2};
  std::cout << arr[4] << '\n';
}

ei andnud mul mingisugust veateadet:

0

See aga ei tähenda, et teistsugune programm, mis massiivi piire ületab, samamoodi toimib. Veelgi enam, isegi sama programm ei pruugi teises arvutis (või teise kompilaatoriga, või mõnikord isegi samades tingimustes) samamoodi toimida. See tähendab, et kui programmis mõni selline viga on, ei pruugi see tingimata lokaalse testimise ja/või väikeste testidega testimise korral välja tulla.

Niisugune massiivi piiride ületamine on näide määramatusest (undefined behavior, UB). Kui programmi koodis midagi sellist on, siis võib programm ilma igasuguste hoiatusteta teha üks kõik mida. Suur osa kompilaatori tööst on optimeerimine, ja optimeerijad on kirjutatud eeldusel, et programmid ei sisalda määramatust. See tähendab, et määramatust sisaldava koodi käitumine võib olla väga ebaintuitiivne.

Mõned näited:

Võistlustel on kõige sagedasem massiivi piiride ületamine. Kuna koodi testimine ei pruugi viga tuvastada, siis kuidas niisugust viga üles leida?

Selleks, et massiivi piiride ületamist ja muid sarnaseid vigu leida, kompileeri oma kood lipuga -fsanitize=address:

g++ -fsanitize=address broken.cpp -o broken

Kui ülaltoodud programmi nüüd uuesti jooksutada, on väljund üsna pikk ja hirmutav:

=================================================================
==770335==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000020 at pc 0x57177d6d661b bp 0x7fffe1b25ef0 sp 0x7fffe1b25ee0
READ of size 4 at 0x502000000020 thread T0
    #0 0x57177d6d661a in main /test/broken.cpp:6
    #1 0x7a8b79c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #2 0x7a8b79c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #3 0x57177d6d6324 in _start (/test/broken+0x2324) (BuildId: 556f7a1cf83216fedd2e49e69184e258cf832d91)

0x502000000020 is located 4 bytes after 12-byte region [0x502000000010,0x50200000001c)
allocated by thread T0 here:
    #0 0x7a8b7a4fe548 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:95
    #1 0x57177d6d7581 in std::__new_allocator<int>::allocate(unsigned long, void const*) /usr/include/c++/13/bits/new_allocator.h:151
    #2 0x57177d6d713e in std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) /usr/include/c++/13/bits/alloc_traits.h:482
    #3 0x57177d6d713e in std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) /usr/include/c++/13/bits/stl_vector.h:381
    #4 0x57177d6d6d0f in void std::vector<int, std::allocator<int> >::_M_range_initialize<int const*>(int const*, int const*, std::forward_iterator_tag) /usr/include/c++/13/bits/stl_vector.h:1692
    #5 0x57177d6d68a4 in std::vector<int, std::allocator<int> >::vector(std::initializer_list<int>, std::allocator<int> const&) /usr/include/c++/13/bits/stl_vector.h:682
    #6 0x57177d6d6598 in main /test/broken.cpp:5
    #7 0x7a8b79c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #8 0x7a8b79c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #9 0x57177d6d6324 in _start (/test/broken+0x2324) (BuildId: 556f7a1cf83216fedd2e49e69184e258cf832d91)

SUMMARY: AddressSanitizer: heap-buffer-overflow /test/broken.cpp:6 in main
Shadow bytes around the buggy address:
  0x501ffffffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x502000000000: fa fa 00 04[fa]fa fa fa fa fa fa fa fa fa fa fa
  0x502000000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==770335==ABORTING

Siin on igasugust huvitavat infot, ja ainuüksi selle väljundi interpreteerimise kohta võiks pidada mitu loengut. Oluline osa on aga kohe alguses:

==770335==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000020 at pc 0x57177d6d661b bp 0x7fffe1b25ef0 sp 0x7fffe1b25ee0
READ of size 4 at 0x502000000020 thread T0
    #0 0x57177d6d661a in main /test/broken.cpp:6
    #1 0x7a8b79c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #2 0x7a8b79c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #3 0x57177d6d6324 in _start (/test/broken+0x2324) (BuildId: 556f7a1cf83216fedd2e49e69184e258cf832d91)

See ütleb: real 6 on midagi valesti. Tõepoolest: rida 6 on see, kus loeti vektori piiridest väljas olevat neljandat elementi.

2.1. Vektorite saneerimine

Vektoritega tuleb aga olla ettevaatlik. Vaatleme järgmist programmi:

#include <iostream>
#include <vector>

using namespace std;

int main () {
  vector<int> arr;
  arr.push_back(0);
  arr.push_back(1);
  arr.push_back(2);
  cout << arr[3] << '\n';
}

Kompileerime selle programmi lipuga -fsanitize=address ja käivitame. Võiks arvata, et juhtub midagi sarnast, nagu eelmine kord. Aga ei juhtu mitte midagi: programm trükib ekraanile mingi arvu ja lõpetab õnnelikult. Miks?

Selleks tuleb aru saada, kuidas std::vector töötab. Kui vektor initsialiseeritakse, on temas ruumi ainult mõnele elemendile. Kui ruum otsa saab, kopeeritakse kogu vektori sisu ümber uude kohta, kus on ruumi (üldjuhul) kaks korda rohkematele elementidele. Nii võtab iga .push_back() keskmiselt kokku ikka \(O(1)\) aega. See tähendab, et enamasti on vektoris ruumi rohkematele elementidele, kui seal tegelikult elemente on.

Pärast esimest .push_back() on vektoris arr ruumi ühele elemendile, pärast teist kahele ja pärast kolmandat neljale elemendile, kuigi vektoris on tegelikult ainult kolm elementi. Koht, kuhu neljas element minema peaks, on seega juba vektorile reserveeritud. AddressSanitizer näeb ka, et aadress on õigele asjale reserveeritud, ja seega ei pahanda, kui sinna ligi pääsetakse. AddressSanitizer "ei tea", et seda aadressi ei ole tegelikult vektori poolt päris lõpuni kasutusele võetud.

GCC-s saab niisuguse saneerimise sisse lülitada lipuga -D_GLIBCXX_SANITIZE_VECTOR:

g++ broken.cpp -D_GLIBCXX_SANITIZE_VECTOR -fsanitize=address -o broken

2.2. Keerulisem näide

Vaatleme üht salakavalamat näidet:

#include <vector>

struct Trie;
std::vector<Trie> heap;

struct Trie {
  int child_index = -1;
  
  void add (int depth) {
    if (depth == 0)
      return;

    if (child_index == -1) {
      child_index = heap.size();
      heap.push_back(Trie());
    }

    heap[child_index].add(depth-1);
  }
};

int main () {
  Trie root;
  root.add(2);
}

Ka selles programmis on viga, mis ei pruugi testimisel alati välja tulla. Kui seda programmi niisama jooksutada, ei teki ekraanile mingit veateadet. Samas on tegu lihtsustatud versiooniga programmist, mis võistluse ajal ettearvamatult käitus. Kompileerides lipuga -fsanitize=address saame väljundi:

=================================================================
==781694==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010 at pc 0x60df17855830 bp 0x7ffe7849ea30 sp 0x7ffe7849ea20
READ of size 4 at 0x502000000010 thread T0
    #0 0x60df1785582f in Trie::add(int) /test/trie.cpp:18
    #1 0x60df17855862 in Trie::add(int) /test/trie.cpp:18
    #2 0x60df17855474 in main /test/trie.cpp:24
    #3 0x727ea9c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #4 0x727ea9c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #5 0x60df178552e4 in _start (/test/a.out+0x12e4) (BuildId: fabdea7c9974b4a315046e22a8903d6fa39528bb)

0x502000000010 is located 0 bytes inside of 4-byte region [0x502000000010,0x502000000014)
freed by thread T0 here:
    #0 0x727eaa4ff5e8 in operator delete(void*, unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:164
    #1 0x60df178565ca in std::__new_allocator<Trie>::deallocate(Trie*, unsigned long) /usr/include/c++/13/bits/new_allocator.h:172
    #2 0x60df17855b77 in std::allocator_traits<std::allocator<Trie> >::deallocate(std::allocator<Trie>&, Trie*, unsigned long) /usr/include/c++/13/bits/alloc_traits.h:517
    #3 0x60df17855b77 in std::_Vector_base<Trie, std::allocator<Trie> >::_M_deallocate(Trie*, unsigned long) /usr/include/c++/13/bits/stl_vector.h:390
    #4 0x60df178562de in void std::vector<Trie, std::allocator<Trie> >::_M_realloc_insert<Trie>(__gnu_cxx::__normal_iterator<Trie*, std::vector<Trie, std::allocator<Trie> > >, Trie&&) /usr/include/c++/13/bits/vector.tcc:519
    #5 0x60df17855d70 in Trie& std::vector<Trie, std::allocator<Trie> >::emplace_back<Trie>(Trie&&) /usr/include/c++/13/bits/vector.tcc:123
    #6 0x60df17855a29 in std::vector<Trie, std::allocator<Trie> >::push_back(Trie&&) /usr/include/c++/13/bits/stl_vector.h:1299
    #7 0x60df178557e3 in Trie::add(int) /test/trie.cpp:15
    #8 0x60df17855862 in Trie::add(int) /test/trie.cpp:18
    #9 0x60df17855474 in main /test/trie.cpp:24
    #10 0x727ea9c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #11 0x727ea9c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #12 0x60df178552e4 in _start (/test/a.out+0x12e4) (BuildId: fabdea7c9974b4a315046e22a8903d6fa39528bb)

previously allocated by thread T0 here:
    #0 0x727eaa4fe548 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:95
    #1 0x60df17857071 in std::__new_allocator<Trie>::allocate(unsigned long, void const*) /usr/include/c++/13/bits/new_allocator.h:151
    #2 0x60df17856a94 in std::allocator_traits<std::allocator<Trie> >::allocate(std::allocator<Trie>&, unsigned long) /usr/include/c++/13/bits/alloc_traits.h:482
    #3 0x60df17856a94 in std::_Vector_base<Trie, std::allocator<Trie> >::_M_allocate(unsigned long) /usr/include/c++/13/bits/stl_vector.h:381
    #4 0x60df17856087 in void std::vector<Trie, std::allocator<Trie> >::_M_realloc_insert<Trie>(__gnu_cxx::__normal_iterator<Trie*, std::vector<Trie, std::allocator<Trie> > >, Trie&&) /usr/include/c++/13/bits/vector.tcc:459
    #5 0x60df17855d70 in Trie& std::vector<Trie, std::allocator<Trie> >::emplace_back<Trie>(Trie&&) /usr/include/c++/13/bits/vector.tcc:123
    #6 0x60df17855a29 in std::vector<Trie, std::allocator<Trie> >::push_back(Trie&&) /usr/include/c++/13/bits/stl_vector.h:1299
    #7 0x60df178557e3 in Trie::add(int) /test/trie.cpp:15
    #8 0x60df17855474 in main /test/trie.cpp:24
    #9 0x727ea9c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #10 0x727ea9c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #11 0x60df178552e4 in _start (/test/a.out+0x12e4) (BuildId: fabdea7c9974b4a315046e22a8903d6fa39528bb)

SUMMARY: AddressSanitizer: heap-use-after-free /test/trie.cpp:18 in Trie::add(int)
Shadow bytes around the buggy address:
  0x501ffffffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x502000000000: fa fa[fd]fa fa fa 00 fa fa fa fa fa fa fa fa fa
  0x502000000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==781694==ABORTING

Real 18 loetakse midagi, mis on varasemalt real 15 .push_back() tegemise tagajärjel vabastatud. Mis toimub?

Lahendus

Esiteks meenutame, et vektorile .push_back() tegemine põhjustab aeg-ajalt kõikide elementide ümber kolimise.

Programmiga on samaväärne järgmine programm:

#include <vector>

struct Trie {
  int child_index = -1;
};

std::vector<Trie> heap;
void add (Trie *node, int depth) {
  if (depth == 0)
    return;

  if (node->child_index == -1) {
    node->child_index = heap.size();
    heap.push_back(Trie());
  }

  add(&heap[node->child_index], depth-1);
}

int main () {
  Trie root;
  add(&root, 2);
}

Real 14 tehakse heap.push_back(Trie()). Kui vektori heap maht on täis, siis kopeeritakse selle sisu üle uute kohta ja vanad aadressid vabastatakse. Pointer node ise viitab ühele heap elemendile, mille push_back nüüd invalideerib. Seega real 18 node->child_index välja kutsumine on nüüd määramatus.

Analoogiliselt lipule -fsanitize=address saab kasutada lippu -fsanitize=undefined, millega saab avastada muid määramatusi, näiteks märgiga täisarvude ületäitumist. Mõlemad lipud teevad aga programmi aeglasemaks, seega tasub neid kasutada ainult vigade otsimise ajal.

Windowsis need meetodid MinGW või CygWin peal jooksva g++ peal ei toimi. Kui on WSL, siis pole probleemi.

3. Stress-testimine

Programmis tekkinud vea parandamine on kõvasti lihtsam, kui õnnestub see viga kõigepealt reprodutseerida. See tähendab: leida mõni test, kus programmi väljund ei ole see, mis ta olema peaks. Ei ole oluline, kas programm sai vale vastuse või töö katkestati veateatega. Samuti ei ole oluline, kas programmis on ideeline viga või kõigest implementatsioon katki.

Testi leidmiseks on üldine retsept:

  1. Kirjuta hästi lihtne ja naiivne programm, mis ülesande kindlasti korrektselt ära lahendab. See võib olla ülimalt aeglane — me jooksutame koodi ainult väikestel testidel.
  2. Kirjuta teine programm, mis genereerib ülesande kirjeldusele vastavaid teste.
  3. Võrdle oma programmi ja lihtsa programmi väljundeid tuhandetel väikestel testidel.

Programmi tuleks testida just nimelt tuhandetel väikestel, mitte mõnel suurel. Praktika on näidanud, et enamuse valelahenduste vead tulevad välja juba väikeste testide juures (kui piisavalt palju proovida). Kuna lihtne programm võib olla väga aeglane, ei ole meil paljudel suurtel testidel jooksutamiseks aega. Lisaks tuleb meil pärast testi leidmist ka viga ise üles otsida. Suure testiga vea otsimine on üsna lootusetu.

Teeme läbi näite.

Ülesanne. On \(n\) eset, mis tuleb karpidesse pakkida. Igasse karpi mahub ülimalt kaks eset, ja ühegi karbi kaal ei tohi ületada \(x\) grammi. Kõikide esemete kaalud on teada. Mis on minimaalne võimalik karpide arv?

Sisendi esimesel real on kaks täisarvu \(n\) ja \(x\). Teisel real on \(n\) täisarvu \(p_1, p_2, \ldots, p_k\): esemete kaalud.

\(1 \le n \le 2 \cdot 10^5\), \(1 \le x \le 10^9\), \(1 \le p_i \le x\). [Allikas: CSES 1090]

Võibolla mõnele tuleb järgmine idee:

Sorteerime esemed kaalu järgi kasvavalt. Kui ese ei mahu "praegusesse" karpi, asetame karbi kõrvale ja võtame uue karbi. Vastasel korral paneme eseme praegusesse karpi.

See idee on implementeeritud allpool.

boxes.cpp 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main () {
  int n, x;
  cin >> n >> x;

  vector<int> weights (n);
  for (int i = 0; i < n; i++)
    cin >> weights[i];

  sort(weights.begin(), weights.end());

  int box_count = 1; // kasutatud karpide arv
  int cur_weight = 0; // praeguse karbi kogukaal
  int cur_count = 0; // praegusesse karpi pandud asjade arv

  for (int weight : weights) {
    if (cur_weight + weight > x || cur_count == 2) {
      // ese ei mahu praegusesse karpi
      // alustame uut karpi
      box_count++;
      cur_weight = weight;
      cur_count = 1;
    } else {
      cur_weight += weight;
      cur_count++;
    }
  }

  cout << box_count << '\n';
}

Tuleb aga välja, et see lahendus ei ole korrektne ja annab valesid vastuseid. Me ei tea, kas implementatsioonis on mingi viga või on kogu idee vale. Et veast paremini aru saada, kasutame ülaltoodud protsessi, et leida mõni test, kus see programm vale vastuse annab.

3.1. Lihtne ja naiivne programm

Esimene samm protsessis oli:

  1. Kirjuta hästi lihtne ja naiivne programm, mis ülesande kindlasti korrektselt ära lahendab. See võib olla ülimalt aeglane — me jooksutame koodi ainult väikestel testidel.

Üks võimalus on kasutada rekursiivset variantide läbivaatust. Kirjutame rekursiivse funktsiooni, mis proovib järjest vastusesse kõikvõimalikke paare või üksikuid esemeid lisada.

boxes_naive.cpp 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void rec (const vector<int> &weights, vector<int> &used, int x, int cur_boxes, int &best_boxes) {
  if (*min_element(used.begin(), used.end()) == 1) {
    // base case - kõik esemed kasutatud
    best_boxes = min(cur_boxes, best_boxes);
  }
  
  int n = weights.size();

  // proovime läbi kõik karpidesse panemata esemete paarid
  for (int i = 0; i < n; i++) {
    if (used[i])
      continue;

    for (int j = i + 1; j < n; j++) {
      if (used[j])
        continue;

      if (weights[i] + weights[j] <= x) {
        used[i] = 1;
        used[j] = 1;

        rec(weights, used, x, cur_boxes + 1, best_boxes);

        used[i] = 0;
        used[j] = 0;
      }
    }
  }

  // ...ja üksikud esemed
  for (int i = 0; i < n; i++) {
    if (used[i])
      continue;

    used[i] = 1;
    rec(weights, used, x, cur_boxes + 1, best_boxes);
    used[i] = 0;
  }
}

int main () {
  int n, x;
  cin >> n >> x;

  vector<int> weights (n);
  for (int i = 0; i < n; i++)
    cin >> weights[i];

  vector<int> used (n, 0);
  int best_boxes = n;
  rec(weights, used, x, 0, best_boxes);

  cout << best_boxes << '\n';
}

See programm tuli küll pikem kui algne boxes.cpp, aga see polegi nii oluline. Oluline on see, et:

3.2. Testigeneraator

Teine samm meie protsessis on:

  1. Kirjuta teine programm, mis genereerib ülesande kirjeldusele vastavaid teste.

Selleks võiks kirjutada programmi, mis genereerib juhuslikke teste. Ei ole vaja muretseda selle pärast, et kas juhuslikkus on ikka päris ühtlane vmt. Oluline on see, et see programm suudaks teoorias genereerida mistahes korrektse testi.

Hea on, kui sellele programmile saab ette anda mingid parameetrid, et vajaduse korral saaks proovida erinevate suurustega teste. Neid parameetreid võib anda edasi erinevatel viisidel, aga väga mugav on anda neid käsurea kaudu. Selleks tuleb C++-s main-funktsioonile lisada parameetrid (int argc, char **argv). Pythoni vaste sellele on kasutada sys.argv. Antud juhul on loogilised parameetrid ülesande tekstis olevad \(n\) ja \(x\).

boxes_gen.cpp 
#include <iostream>

using namespace std;

int main (int, char **argv) {
  // esimene parameeter: juhuslikkuse seed  
  // seda on mugav parameetrina ette anda, et vajaduse korral sama testi taastoota
  srand(atoi(argv[1]));

  // teine parameeter: ülesande teksti n
  int n = atoi(argv[2]);

  // kolmas parameeter: ülesande teksti x
  int x = atoi(argv[3]);

  cout << n << " " << x << '\n';
  for (int i = 0; i < n; i++) {
    // iga eseme kaal on arv 1...x
    // genereerime selle juhuslikult

    // rand on üldiselt problemaatiline, aga antud juhul see ei loe
    // meid ei huvita, kas juhuslikkus on ühtlane, eesmärk on lihtsalt
    // proovida paljusid erinevaid teste.
    // kui see ikkagi kripeldama jääb, võib kasutada mt19937
    cout << 1 + rand() % x << " ";
  }
  cout << '\n';
}

Kui see kood kompileerida binaariks boxes_gen, siis väljastab näiteks ./boxes_gen 123 4 5 testi, kus \(n = 4\), \(x = 5\) ja juhuslikkuse seed on 123.

3.3. Võrdlemine

Viimaks:

  1. Võrdle oma programmi ja lihtsa programmi väljundeid tuhandetel väikestel testidel.

Tuhandetel väikestel testidel jooksutamine ei ole muidugi asi, mida käsitsi teha saab. Selle programmi erinevatel testidel käivitamine on asi, mida saab suhteliselt lihtsate vahenditega automatiseerida.

Salvesta faili script.sh kood

for i in `seq 1 100`; do
    # prindib praeguse teksti indeksi
    # mulle meeldib nii teha -- saab progressi näha
    echo $i 

    ./boxes_gen $i 5 4 > input.txt
    ./boxes < input.txt > output.txt
    ./boxes_naive < input.txt > answer.txt

    diff output.txt answer.txt || break
done

Jooksuta käsureal chmod +x script.sh, et anda endale õigused skripti käivitamiseks. Seejärel käivita skript käsuga ./script.sh.

Salvesta faili script.bat kood

@echo off

for /l %%i in (1, 1, 100) do (
    echo %%i

    boxes_gen.exe %%i 5 4 > input.txt
    boxes.exe < input.txt > output.txt
    boxes_naive.exe < input.txt > answer.txt

    fc output.txt answer.txt || goto :out
)

:out

Käivita skript käsuga script.bat.

Salvesta faili script.ps1 kood

foreach ($i in 1..100) {
  echo $i;
  ./boxes_gen $i 6 4 > input.txt;
  Get-Content input.txt | ./boxes > output.txt;
  Get-Content input.txt | ./boxes_naive > answer.txt;
  fc.exe output.txt answer.txt;
  if ($LASTEXITCODE) {
	  break;
  }
}

Käivita skript käsuga ./script.ps1.

Skriptide käivitamine võib olla välja lülitatud. Kui on, siis saab seda sisse lülitada käsuga (vaja administraatori õiguseid)

Set-ExecutionPolicy -ExecutionPolicy Unrestricted

Süntaks võib näida veider, aga pisut edasi vaadates näeme, et tegu on tavalise for-tsükliga. Tsükkel käib läbi kõik täisarvud \(1 \ldots 100\). Iga i kohta käivitatakse programm boxes_gen argumentidega i 5 4, väljund suunatakse faili input.txt. Seejärel käivitatakse mõlemad lahendusprogrammid sisendiga input.txt; väljund suunatakse vastavalt failidesse output.txt ja answer.txt. Viimane käsk (diff või fc) võrdleb omavahel faile output.txt ja answer.txt. Kui need on erinevad, siis käivitub ||-le järgnev break või goto :out, mis väljuvad tsüklist.

Mul leidis skript erinevuse viiendal katsel. Test on järgmine:

5 4
4 2 3 1 1

See on tõepoolest kontratest — ahne lahendus boxes.cpp leiab selles tekstis tükelduse [[1, 1], [2], [3], [4]], seevastu üks võimalik optimaalne paigutus oleks [[1, 2], [1, 3], [4]].

Seda meetodit võib kasutada erinevatel loomingulistel viisidel. Näiteks kui kahtlustad, et programmis on määramatus, võib seda kombineerida ülaltoodud -fsanitize=address lipuga. Sel juhul pole naiivset lahendust vaja: skript vaatab läbi erinevaid teste ja kontrollib, ega ühegi jooksutamisel määramatust ei teki.

g++ program.cpp -fsanitize=address -o program

for i in `seq 1 100`; do
    echo $i

    ./program < input.txt > output.txt || break
done

Määramatuse esinemise korral väljub programm veaga, seetõttu käivitub || järel olev break või goto :out.

4. Tekstipõhine debugger gdb

Programm program debugimiseks käivita käsk gdb program. Üldpõhimõtted on samad, mis IDE-s olevas graafilises debuggeris, aga kõik on tekstipõhine.

Programmi käivitamiseks on käsk run ehk r. Seda saab kombineerida käsureaargumentide ja isegi sisendi suunamisega, näiteks r 12 34 5 < in.txt.

Breakpoint ehk katkepunkti lisamiseks on käsk break <rea number> ehk b <rea number>. Mitmest failist koosneva programmi korral kasuta break failinimi:<rea number>. Katkepunkti eemaldamiseks on käsk delete <katkepunkti number> ehk d <katkepunkti number>.

(gdb) b 10 =

Käsk backtrace ehk bt trükib ekraanile praeguse stack trace ehk pinujälje. Mööda pinujälge üles ja alla liikumiseks on frame <frame number> ehk f.

(gdb) bt =

Käsk print <muutuja nimi> ehk p <muutuja nimi> trükib ekraanile vastava muutuja väärtuse.

(gdb) p cur_boxes =

Käsk next ehk n liigub programmis ühe sammu võrra edasi (ilma funktsioonidesse sisse laskuma). Laskumisega versioon sellest on step ehk s. continue ehk c jätkab programmi tööd järgmise katkepunktini.

=

=

=

Debuggerist väljumiseks on käsk quit ehk q.