Debugging
Ο όρος αποσφαλμάτωση αναφέρεται σε ένα σύνολο τεχνικών που μπορεί κάποιος να χρησιμοποιήσει για να εντοπίσει ένα πιθανό λάθος στον κώδικά του. Συχνά όταν αντιλαμβανόμαστε ότι το πρόγραμμά μας δεν τρέχει σωστά, ή όταν θέλουμε να είμαστε σίγουροι ότι τρέχει σωστά, ακολουθούμε μια διαδικασία. Πρέπει να πούμε πως το debugging στοχεύει να εντοπίσει και να λύσει λάθη στην υλοποίηση και όχι στην αλγοριθμική σύλληψη, οπότε σπάνια θα βοηθήσει σε αυτόν τον τομέα. Εάν υπάρχει περίπτωση να έχουμε λάθος σύλληψη, καλό θα ήταν να γυρίσουμε στο χαρτί και το μολύβι.
- Επιθεώρηση κώδικα
- Προειδοποιήσεις μεταγλωττιστή
- Δημιουργία αρχείων ελέγχου
- Χρησιμοποιώντας debugger
- Πηγές
Επιθεώρηση κώδικα
Σε πρώτη φάση μπορούμε να ρίξουμε άλλη μια ματιά στον κώδικά μας και να ψάξουμε για συχνά λάθη. Αν και δεν συστήνεται να στηριζόμαστε σε αυτό ή να χάνουμε πολύ χρόνο, πολλά λάθη μπορούν να εντοπιστούν αμέσως με αυτόν τον τρόπο.
Προειδοποιήσεις μεταγλωττιστή
Πολλές φορές ο compiler θα μας προειδοποιήσει ότι σε κάποια γραμμή υπάρχει ένα συγκεκριμένο πρόβλημα. Άλλες φορές όμως θα τα προσπεράσει χωρίς να μας ενημερώσει. Πολλά λάθη μπορούν να αποφευχθούν εάν χρησιμοποιήσουμε την ρύθμιση -W όταν κάνουμε compile (δηλαδή g++ source.cpp -W), έτσι ώστε ο compiler να μας προειδοποιεί για περισσότερα πιθανά σφάλματα.
Δημιουργία αρχείων ελέγχου
Εάν γνωρίζουμε ότι ο κώδικάς μας δεν είναι σωστός (πχ δεν γίνεται δεκτός από τον grader), είναι ιδιαίτερα βοηθητικό να δημιουργήσουμε τυχαία testcases. Κάτι τέτοιο μπορεί να μας βοηθήσει να βρούμε περιπτώσεις που το πρόγραμμά μας δεν είναι αρκετά αποδοτικό και βγαίνει έξω από τα όρια χρόνου ή μνήμης. Σε περίπτωση που προσπαθούμε να εντοπίσουμε πρόβλημα λάθος απάντησης, η πιο συνηθισμένη λύση είναι να γράψουμε και μια πιο αργή και απλή λύση (naive) και να συγκρίνουμε τις απαντήσεις των δύο προγραμμάτων.
Γράφοντας τον testcase generator
Χρήσιμες βιβλιοθήκες της c/c++ που βοηθούν στην δημιουργία τυχαίων αρχείων ελέγχου είναι οι stdlib.h και η time.h. Ας κοιτάξουμε όμως ένα συγκεκριμένο παράδειγμα.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int N, MAXNUM;
srand(time(NULL));
scanf("%d %d", &N, &MAXNUM);
for(int i=1; i<=N; i++) {
printf("%d ", rand()%MAXNUM+1);
}
printf("\n");
return 0;
}
Το πρόγραμμα αυτό διαβάζει δυο παραμέτρους, N και MAXNUM, και τυπώνει N τυχαίους αριθμούς σε μια σειρά οι οποίοι είναι από το 1 μέχρι το MAXNUM. Η γραμμή srand(time(NULL)) αρχικοποιεί τον random number generator της C. Έπειτα, η συνάρτηση rand() επιστρέφει έναν τυχαίο ακέραιο αριθμό, τον οποίο περιορίζουμε στο όριο που χρειαζόμαστε κρατώντας το υπόλοιπο της Ευκλείδειας διαίρεσης με το MAXNUM (και αυξάνοντας κατά 1).
Αν και αυτό ήταν ένα πρόβλημα στο οποίο ήταν εύκολο να δημιουργήσουμε αρχεία ελέγχου, είναι ενδεικτικό της χρήσης της συνάρτησης rand().
Εντοπισμός απλών σφαλμάτων με τη χρήση αρχείων ελέγχου
Εάν έχουμε κάποιο αρχείο ελέγχου στο οποίο γνωρίζουμε ότι το πρόγραμμά μας δεν έχει το επιθυμητό αποτέλεσμα (λάθος απάντηση, ή άλλο πρόβλημα), μπορούμε πιο εύκολα να εντοπίσουμε το σφάλμα μας.
Σφάλμα κατάτμησης ή υπέρβασης χρονικού ορίου
Αν και αυτά τα προβλήματα λύνονται ευκολότερα με τη χρήση debugger, υπάρχει και άλλος τρόπος να εντοπιστούν. Σε περίπτωση που έχουμε σφάλμα κατάτμησης, συχνά κοιτάμε μήπως υπερβαίνουμε τα όρια κάποιου πίνακα, δηλαδή προσπαθούμε να χρησιμοποιήσουμε μνήμη που υπερβαίνει τα όρια που έχουμε θέσει. Σε περίπτωση που υπερβαίνεται το χρονικό όριο κατά πολύ (πρέπει να χρησιμοποιήσουμε keyboard interrupt για να σταματήσει το πρόγραμμα), συνήθως υποψιαζόμαστε την ύπαρξη κάποιου infinite loop, το οποίο μπορεί να προκληθεί είτε από κάποια δομή επανάληψης προβληματική (for ή while) ή από κάποια αναδρομή. Για να εντοπίσουμε σε ποιο σημείο του προγράμματος βρίσκεται το πρόβλημα, μπορούμε να τυπώνουμε σε κάποια κομβικά σημεία μια φράση ελέγχου (πχ printf("moxos\n");), και να εξετάζουμε από ποια σημεία κατάφερε να περάσει το πρόγραμμα. Εάν όμως το πρόγραμμά μας είναι αργό χωρίς να έχει infinite loop, πολλές φορές έχουμε υλοποιήσει έναν αργό αλγόριθμο με υψηλή πολυπλοκότητα.
Λάθος απάντηση
Εάν γνωρίζουμε ότι σε ένα συγκεκριμένο testcase το πρόγραμμά μας επιστρέφει τη λάθος απάντηση, αρχικά μπορούμε να επανεξετάσουμε τον κώδικα, έχοντας κατά νου τι μπορεί να προκάλεσε την λάθος απάντηση. Συχνά κάτι τέτοιο μπορεί να μην φέρει αποτέλεσμα. Εάν το αρχείο ελέγχου είναι υπερβολικά μεγάλο για να το επεξεργαστούμε με το χέρι, μπορούμε να εντοπίσουμε το κομμάτι που δημιουργεί το πρόβλημα και να το απομονώσουμε (εάν το πρόβλημα το επιτρέπει). Το πιο δραστικό μέτρο που μπορούμε να πάρουμε εάν το πρόγραμμά μας επιστρέφει λάθος απάντηση, είναι να τυπώνουμε σε διάφορα σημεία τις μεταβλητές μας. Με αυτόν τον τρόπο, ακολουθούμε την διαδικασία του προγράμματος και κοιτάζουμε σε ποιο σημείο κάποια μεταβλητή παίρνει λάθος τιμή. Έτσι, εντοπίζουμε το σημείο στο οποίο έγινε το λάθος και μπορούμε να το διορθώσουμε.
Χρησιμοποιώντας debugger
Ένα από τα πιο χρήσιμα εργαλεία στην αποσφαλμάτωση είναι η χρήση debugger. Ο debugger που χρησιμοποιείται σε πιο ευρεία κλίμακα στο διαγωνιστικό επίπεδο είναι ο gdb (Gnu DeBugger). Παρέχει κάποια βασικά εργαλεία που μπορούν να διευκολύνουν σε μεγάλο βαθμό τη διαδικασία της αποσφαλμάτωσης. Ο καλύτερος τρόπος να χρησιμοποιήσουμε τον debugger είναι μέσα από ένα παράδειγμα.
#include <stdio.h>
int N, a[10];
int main() {
scanf("%d", &N);
for(int i=1; i<=N; --i) {
scanf("%d", &a[i]);
}
int mn=a[1];
for(int i=1; i<=N; ++i) {
if(mn<a[i]); {
mn=a[i];
}
}
printf("%d\n", mn);
}
Κάνοντας βέβαια compile με τη χρήση της ρύθμισης -W θα εντοπίσουμε αμέσως το σφάλμα στην if μέσα στη 2η for. Οπότε ας διορθώσουμε αυτό το λάθος:
#include <stdio.h>
int N, a[10];
int main() {
scanf("%d", &N);
for(int i=1; i<=N; --i) {
scanf("%d", &a[i]);
}
int mn=a[1];
for(int i=1; i<=N; ++i) {
if(mn<a[i]) {
mn=a[i];
}
}
printf("%d\n", mn);
}
Εκτελώντας αυτόν τον κώδικα θα παρατηρήσουμε ότι αν δώσουμε στο N μια τιμή (έστω 1), θα διαβάσει παραπάνω αριθμούς το πρόγραμμα μας, και κάποια στιγμή θα μας ειδοποιήσει ότι υπήρξε σφάλμα κατάτμησης (Segmentation Fault). Παρόλο που στο συγκεκριμένο παράδειγμα το λάθος είναι σχετικά εύκολο να εντοπιστεί ας δούμε πώς θα μας βοηθούσε ο gdb.
Αφού έχουμε μεταγλωττίσει (compile) τον κώδικά μας, έχει παραχθεί το εκτελέσιμο αρχείο. Για να μπορέσει ο gdb και οποιοσδήποτε debugger να διαβάσει σωστά το εκτελέσιμο αρχείο, θα πρέπει να συμπεριλάβουμε την ρύθμιση -g όταν κάνουμε compile (δηλαδή g++ source.cpp -g). Αφού παραχθεί το εκτελέσιμο αρχείο, τρέχουμε (στην γραμμή εντολών των Linux πάντα) την εντολή gdb ./a.out (ή όπως αλλιώς έχουμε ονομάσει το εκτελέσιμο). Έπειτα θα εμφανιστεί μια οθόνη παρόμοια με την εξής:
$ gdb ./a.out
GNU gdb (Ubuntu 7.10-1ubuntu2) 7.10
Copyright (C) 2015 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./a.out...done.
(gdb)
(Για να μην μας ενοχλεί το μεγάλο κείμενο, μπορούμε να πατήσουμε Ctrl-L έτσι ώστε να καθαρίσει η οθόνη)
Για να εκτελεστεί το πρόγραμμα όπως θα εκτελούνταν και από την γραμμή εντολών γράφουμε run και έπειτα δίνουμε τα στοιχεία εισόδου.
(gdb) run
Starting program: /home/user/Desktop/a.out
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Program received signal SIGSEGV, Segmentation fault.
0x00000011f71d9c40 in ?? ()
Δυστυχώς ο debugger δεν εντόπισε αμέσως την γραμμή στην οποία υπάρχει το πρόβλημα. Αν και συνήθως αυτό το βήμα δεν χρειάζεται, για να αναλύσουμε το segmentation fault θα χρησιμοποιήσουμε την εντολή backtrace.
(gdb) backtrace
#0 0x00000011f71d9c40 in ?? ()
#1 0x000000000040067d in main () at source.cpp:8
Μπορούμε λοιπόν να καταλάβουμε ότι το πρόβλημα συμβαίνει στη γραμμή 8 του κώδικά μας. Αν και μπορούμε να επιστρέψουμε στον editor για να κοιτάξουμε τη γραμμή αυτή, ο gdb μας δίνει τη δυνατότητα να κοιτάξουμε τον κώδικά μας με την εντολή list ή list LINENUM όπου LINENUM βάζουμε το νούμερο της γραμμής. Σε αυτήν την περίπτωση θα γράψουμε list 8, για να μας δείξει τις γραμμές του κώδικά μας κοντά στη γραμμή 8.
(gdb) list 8
3 int N, a[10];
4
5 int main() {
6 scanf("%d", &N);
7 for(int i=1; i<=N; --i) {
8 scanf("%d", &a[i]);
9 }
10
11 int mn=a[1];
12 for(int i=1; i<=N; ++i) {
Κοιτάζοντας την γραμμή 8, μπορούμε να συμπεράνουμε ότι σε εκείνο το σημείο βγαίνουμε εκτός ορίων του πίνακα a[i]. Εάν κοιτάξουμε προσεκτικά λοιπόν τον κώδικα κοντά στη γραμμή αυτή θα εντοπίσουμε το μικρό λάθος που προκαλεί το segmentation fault. Αντί να αυξάνει το i, μειώνεται, και κάποια στιγμή γίνεται αρνητικό, φεύγοντας από τα όρια του πίνακα. Αξίζει να σημειωθεί πως το πρόγραμμα δεν σταματάει αμέσως μόλις φύγει από το όριο του πίνακα.
Αφού διορθώσουμε το λάθος αυτό, ο κώδικάς μας θα γίνει ως εξής:
#include <stdio.h>
int N, a[10];
int main() {
scanf("%d", &N);
for(int i=1; i<=N; ++i) {
scanf("%d", &a[i]);
}
int mn=a[1];
for(int i=1; i<=N; ++i) {
if(mn<a[i]) {
mn=a[i];
}
}
printf("%d\n", mn);
}
Αφού μεταγλωττίσουμε την καινούρια αυτή έκδοση, θα δούμε ότι το πρόγραμμα τρέχει ομαλά. Δοκιμάζοντας όμως μερικά μικρά αρχεία ελέγχου θα παρατηρήσουμε ότι το πρόγραμμά μας επιστρέφει τη λάθος απάντηση. Αν και σε αυτό το σημείο θα βοηθούσε να τυπώνουμε τις μεταβλητές, θα δούμε πώς μπορεί να βοηθήσει ο gdb.
Ο gdb μας δίνει τη δυνατότητα να σταματήσουμε την εκτέλεση του προγράμματος όταν φτάσει σε κάποιο σημείο (πχ σε μια συγκεκριμένη γραμμή). Για να το κάνουμε αυτό χρησιμοποιούμε τα λεγόμενα “breakpoints”, δηλαδή σημεία στα οποία σταματάει το πρόγραμμα. Για να ορίσουμε ένα breakpoint στην γραμμή 5 θα γράφαμε break 5. Αφού σταματήσει το πρόγραμμά μας έχουμε τη δυνατότητα να τυπώσουμε μεταβλητές με την εντολή print. Για να συνεχίσει το πρόγραμμά μας κανονικά μπορούμε να χρησιμοποιήσουμε την εντολή continue, και για να συνεχίσει βαθμιαία (δηλαδή βήμα-βήμα), την εντολή next. Ας το δούμε στην πράξη:
(gdb) break 10
Breakpoint 1 at 0x4005db: file source.cpp, line 10.
(gdb) run
Starting program: /home/user/Desktop/a.out
5
1 2 3 4 5
Breakpoint 1, main () at source.cpp:11
11 int mn=a[1];
(gdb) print a
$1 = {0, 1, 2, 3, 4, 5, 0, 0, 0, 0}
Παρατηρούμε ότι ο gdb χειρίζεται τους πίνακες αρκετά καλά, καθώς τυπώνει ολόκληρο τον πίνακα a σε μια κατανοητή μορφή. Παρατηρούμε επίσης ότι το πρόγραμμα έχει σταματήσει στην γραμμή 10, οπότε η γραμμή 11 (που τύπωσε ο gdb) δεν έχει εκτελεστεί ακόμα.
(gdb) next
12 for(int i=1; i<=N; ++i) {
(gdb) print mn
$2 = 1
Συνεχίζοντας παρατηρούμε ότι η γραμμή 11 δούλεψε σωστά, δηλαδή το min πήρε την τιμή του a[1] όπως θα έπρεπε.
(gdb) next
13 if(mn<a[i]) {
(gdb) next
12 for(int i=1; i<=N; ++i) {
Παρακάτω παρατηρούμε ότι η γραμμή 14 δεν εκτελέστηκε, αφού δεν ίσχυε η συνθήκη του if, και το πρόγραμμα επέστρεψε στη γραμμή 12.
(gdb) next
13 if(mn<a[i]) {
(gdb) next
14 mn=a[i];
(gdb) next
12 for(int i=1; i<=N; ++i) {
(gdb) print mn
$3 = 2
Συνεχίζοντας όμως την εκτέλεση, εντοπίζουμε το λάθος. Στην επόμενη επανάληψη, η συνθήκη ισχύει και η τιμή του mn γίνεται 2. Όμως το mn υποτίθεται ότι κρατάει το ελάχιστο στοιχείο, οπότε δεν έπρεπε να αυξηθεί, επομένως η συνθήκη είναι λάθος. Παρατηρούμε πως η συνθήκη προκαλεί το mn να πάρει την μέγιστη τιμή αντί για την ελάχιστη, οπότε αρκεί να διορθώσουμε την γραμμή 13.
Ο κώδικας θα γίνει ως εξής:
#include <stdio.h>
int N, a[10];
int main() {
scanf("%d", &N);
for(int i=1; i<=N; ++i) {
scanf("%d", &a[i]);
}
int mn=a[1];
for(int i=1; i<=N; ++i) {
if(mn>a[i]) {
mn=a[i];
}
}
printf("%d\n", mn);
}
Σε αυτό το σημείο μπορεί να νομίσουμε ότι όλα πάνε καλά. Υποβάλλοντας όμως το πρόβλημα θα ειδοποιηθούμε ότι αντιμετωπίσαμε σφάλμα κατάτμησης σε κάποια αρχεία ελέγχου. Δημιουργώντας τυχαία δικά μας αρχεία ελέγχου, καταλήξαμε σε ένα αρχείο ελέγχου το οποίο αναπαράγει το segmentation fault στον υπολογιστή μας. Έστω ότι το αρχείο αυτό ονομάζεται input.
Εκτελώντας το πρόγραμμά μας με το input θα δούμε το εξής:
$ ./a.out < input
Segmentation fault (core dumped)
Ας χρησιμοποιήσουμε πάλι τον gdb.
(gdb) run < input
Starting program: /home/user/Desktop/a.out < input
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7a6c52a in _IO_vfscanf_internal (s=<optimized out>,
format=<optimized out>, argptr=argptr@entry=0x7fffffffdd28,
errp=errp@entry=0x0) at vfscanf.c:1826
1826 vfscanf.c: No such file or directory.
(gdb) backtrace
#0 0x00007ffff7a6c52a in _IO_vfscanf_internal (s=<optimized out>,
format=<optimized out>, argptr=argptr@entry=0x7fffffffdd28,
errp=errp@entry=0x0) at vfscanf.c:1826
#1 0x00007ffff7a7acdb in __scanf (format=<optimized out>) at scanf.c:33
#2 0x00000000004005d5 in main () at source.cpp:8
Το backtrace μας δίνει την πληροφορία ότι το πρόβλημα βρίσκεται πάλι στην γραμμή 8 του προγράμματός μας. Υποψιαζόμαστε ότι πάλι βγαίνουμε εκτός ορίων του πίνακα a κατά το διάβασμα του.
(gdb) print a
$1 = {0, 10, 10, 10, 10, 10, 10, 10, 10, 10}
(gdb) print N
$2 = 1000
Τυπώνοντας τις μεταβλητές μας μέχρι εκείνο το σημείο οι υποψίες μας επαληθεύονται. Προσπαθούμε να διαβάσουμε 1000 στοιχεία μέσα σε έναν πίνακα με 10 (ουσιαστικά 9) θέσεις! Σε αυτό το σημείο αντιλαμβανόμαστε ότι τα δεδομένα του προβλήματος απαιτούν μεγαλύτερο μέγεθος πίνακα. Αλλάζοντας για μία τελευταία φορά τον κώδικά μας καταλήγουμε στην τελική του μορφή:
#include <stdio.h>
int N, a[10000000];
int main() {
scanf("%d", &N);
for(int i=1; i<=N; ++i) {
scanf("%d", &a[i]);
}
int mn=a[1];
for(int i=1; i<=N; ++i) {
if(mn>a[i]) {
mn=a[i];
}
}
printf("%d\n", mn);
}
Υποβάλλοντας τον κώδικα αυτό παρατηρούμε ότι είναι σωστός. Πρέπει να σημειωθεί ότι η διαδικασία αυτή σε πραγματικές συνθήκες θα έπαιρνε πολύ λιγότερο χρόνο από ό,τι φαίνεται. Επιπλέον, τέτοια λάθη όπως αυτά που παρουσιάζονται εδώ αποφεύγονται με την εξάσκηση. Αν και καλό είναι να γνωρίζουμε να τα εντοπίζουμε, ο καλύτερος τρόπος αντιμετώπισης είναι η εξάσκηση για να μην τα κάνουμε καν.