// here is some code for demonstrating some testing-related concepts // we will also use this code to investigate profiling next week. #include #include // a basic (slow) primality tester // precondition: x >= 2 // postcondition: return value is 1 if x is prime, 0 otherwise // statement coverage: need 2 tests, 1 prime 1 not // branch coverage: need 3 tests x==2, 1 other prime 1 not // total coverage on attu: 2^32 tests (and it takes 1 int) int is_prime(int x) { int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } // what if is_prime did an illegal-free but didn't crash: // black-box testing: very unlikely to discover the bug // white-box testing: depends on test "harness" whether illegal free is // detected? int is_prime2(int x) { if(x==8675308) free((int*)8675308); int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } // for a large number, how can you check that the result is right: // * write a function that checks // * for is_prime that is as much work (and as error-prone) // * but for a faster primality tester (e.g., Sieve of Erastothenes), // is_prime would be a great checker // a more realistic buggy version where white-box testing might be better int is_prime3(int x) { if(x > 13) { int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } return x==2 || x==3 || x==5 || x==7 || x==11; } // find the largest element of nums such that the correpsonding element of // is_allowed is 1 // precondition: nums, is_allowed not NULL, arrlen is length of both // (okay for nums ans is_allowed to be aliases) // postcondition: result is -1 if no element of is_allowed is 1, // else result is largest nums[i] such that is_allowed[i] is 1 int find_largest(int arrlen, int * nums, int * is_allowed) { if(arrlen==0) return -1; if(!is_allowed[arrlen-1]) return find_largest(arrlen-1,nums,is_allowed); if(find_largest(arrlen-1,nums,is_allowed) > nums[arrlen-1]) return find_largest(arrlen-1,nums,is_allowed); return nums[arrlen-1]; } // testing ideas: // * do not choose nums randomly, may never be sorted // or reverse-sorted or have-no-primes // * try very short arrays and very long arrays // * try arrays with repeats // * full coverage impossible; possible for very short arrays // return a new heap-allocated array where result[i] is 1 if // arr[i] is prime, else 0 // ... // how could we test this before is_prime is written? int * find_primes(int arrlen, int * arr) { int * ans = (int*)calloc(arrlen,sizeof(int)); int i=0; for(; i < arrlen; ++i) if(is_prime(arr[i])) // how to stub the call to is_prime? ans[i] = 1; return ans; } // approach: pre-computed answers int is_prime_stub1(int x) { int answers[10][2] = {{2,1},{3,1},{4,0},{5,1},{13,1},{35,0},{51,0},{9,0},{17,1},{20,0}}; int i=0; for(; i < 10; ++i) if(answers[i][0]==x) return answers[i][1]; fprintf(stderr,"is_prime_stub1: unsupported argument"); exit(1); } // approach: lie in a way that does not affect caller int is_prime_stub2(int x) { return x > 20; }