Automatic Test Case Simplification Tool

I tell Huiqi about an tool I made to automate the tedious process of a debugging technique called test case simplification (https://www.youtube.com/watch?v=zkT1DILY7e4).

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : yeah all right uh what what about that
00:03 : you you can show me the new tool that
00:05 : you made
00:06 : for the uh this tool
00:09 : um sure um i made this
00:14 : automatic test case simplification tool
00:18 : called uh well it's simplified
00:21 : testcase.pi
00:22 : and um i've
00:25 : been pretty happy with with it so test
00:28 : case simplification
00:30 : i guess so test case simplification
00:34 : is is when you you have like some
00:37 : weird error but you you know it's coming
00:40 : from this file
00:42 : but you don't know exactly where from
00:44 : this file
00:46 : or or not not necessarily a file but in
00:49 : in this this tool only works with a file
00:52 : but it could be for example
00:56 : why uh like this
00:59 : entire code base like
01:02 : it's generating some very weird error
01:05 : the error is not telling me where it is
01:08 : coming from
01:10 : i just know that this very weird error
01:13 : so what you do is you try to simplify
01:16 : this test case to the bare minimum
01:21 : that still generates this very weird
01:23 : error
01:24 : and then now you have less stuff to look
01:26 : at
01:27 : and um actually yeah if
01:31 : i made a video right uh on debug school
01:35 : it's on youtube uh just
01:38 : if if anybody is interested
01:41 : uh i made a video about that
01:45 : is you go to debug school.com
01:48 : number five test case simplification i
01:50 : have a more in-depth
01:52 : uh explanation of what that is
01:55 : and this is a technique i use a lot um
02:00 : whenever i i really want to solve
02:03 : a bug uh and the error message is not
02:07 : giving me any help
02:08 : i i use this a lot um
02:11 : and then a couple days ago i decided to
02:15 : make a tool
02:16 : that does this automatically for me so
02:19 : because usually this is a very tedious
02:21 : process
02:22 : right it usually is like oh god i have
02:25 : like a very large
02:26 : file i'm gonna selectively delete
02:30 : chunks of it
02:31 : [Music]
02:33 : maybe i'll um
02:36 : so so maybe like
02:39 : to show an example of this let's say i
02:43 : have
02:43 : a file like this uh wait are you sharing
02:46 : a screen
02:47 : or oh let me share my screen
02:50 : sure
03:00 : okay can you see my screen
03:05 : yes okay so
03:08 : yeah so let's say i have a file like
03:11 : this
03:12 : uh i'm calling this file test2.pi
03:18 : okay and and just to introduce an
03:21 : error here maybe i
03:24 : maybe i forgot to close this parenthesis
03:28 : right um now for the case of python we
03:32 : actually do get a
03:33 : kind of a the error message is
03:36 : good enough in python that you can
03:39 : normally figure it out
03:41 : but let's say let's say let's pretend
03:44 : it's a more cryptic one
03:46 : so let's say you couldn't figure it out
03:48 : so if
03:48 : [Music]
03:52 : but i was using this with
03:55 : you know more cryptic error messages
03:58 : and and it worked very well so far i'm
04:01 : pretty happy with it
04:02 : so so it gives us this error message it
04:05 : says
04:06 : uh line 170. it's pointing to the next
04:09 : line
04:11 : to the one where i made a mistake right
04:14 : so to some people that might be very
04:16 : cryptic
04:17 : and they're like what i'm looking at
04:19 : this log file i don't see anything wrong
04:21 : so so they have no idea what's going on
04:24 : right maybe they didn't think to look at
04:26 : the previous line
04:27 : for this pick um so
04:31 : what you could do if you had this tool
04:34 : is um you
04:38 : first you write a execute function i
04:41 : have a couple of them here
04:43 : i haven't extracted this out to be a
04:45 : reusable tool just yet because i
04:47 : okay i just made it two days ago but um
04:50 : but the idea is you write an execute
04:53 : function
04:54 : which if you ran the function it returns
04:58 : true if and only if
05:02 : that cryptic error is happening
05:05 : and it returns false if that
05:08 : cryptic error is not happening okay
05:12 : and so the way i'm gonna do that is by
05:16 : running this command
05:18 : [Music]
05:20 : i think this does that so this runs
05:23 : python3 and then this file
05:26 : i'm typing python but is same as python3
05:30 : in this case
05:31 : so so i'm getting python to do the same
05:34 : thing i'm doing on
05:36 : my command line and then and then i'm
05:40 : actually going to
05:43 : decode these in this case
05:46 : it should be the error
05:50 : i'm going to assume it first of all
05:53 : the cryptic error presumes that
05:57 : the return code is one return code is
06:00 : one means
06:01 : the program has failed and weather
06:05 : so i'm gonna say if it's zero if the
06:08 : program
06:09 : went through with no error that's
06:12 : actually a false
06:13 : that's a absence of the cryptic error
06:17 : okay and then i'm gonna say i'm gonna
06:20 : decode the standard error that error
06:23 : message that get printed out
06:24 : i'm gonna grab it i'm gonna split it
06:28 : into the error lines and
06:31 : for now i'll print it out to to to know
06:34 : what to match
06:36 : and then i'm gonna test out my execute
06:39 : three function first
06:40 : before i use this tool on it
06:46 : okay so these are my error lines right
06:48 : so
06:49 : i'm saying hey this is my cryptic error
06:51 : and i want to
06:52 : match this cryptic error i want to say
06:54 : if this is true
06:55 : about my error message then yes
06:58 : i'm seeing this cryptic error so what
07:01 : i'm going to do is say
07:02 : hey if um
07:06 : if how about if this line says syntax
07:09 : error
07:10 : invalid syntax and this would be
07:12 : negative 2
07:14 : index negative two for python because
07:16 : python can have
07:17 : negative index oh
07:20 : okay so airlines negative two
07:23 : is the second from the back all right
07:28 : if the second from the back is
07:31 : syntax error invalid syntax and then
07:35 : this is the third one the fourth from
07:37 : the back
07:38 : is lock file dot flush okay
07:43 : yeah like negative syntax i mean
07:45 : negative index that's
07:47 : nice i'm gonna say match one is that
07:50 : match
07:50 : two if both of these conditions match
07:53 : then i'm gonna say that is the signature
07:56 : for my cryptic
07:58 : error okay so i'm gonna say
08:02 : uh match one and
08:05 : match two if if both of these
08:09 : lines match then the the cryptic error
08:13 : exists so let's see
08:16 : and i'm gonna print the result of this
08:20 : function it says
08:23 : true and okay if i remove this error or
08:27 : if it's like a different
08:29 : if i remove the error it says false
08:32 : different error then it's false but
08:35 : but only if i made this error then it's
08:38 : true
08:38 : okay okay so that that's what you're
08:41 : supposed
08:42 : how you're supposed to implement your
08:44 : execute function now once you have this
08:46 : execute function you plug it into this
08:49 : simplify test case
08:52 : function it's execute three
08:55 : and then you tell it the file
08:59 : that is the input to this that that you
09:02 : know
09:02 : goes into this test case
09:05 : which is this test test2.pi file and
09:08 : then you start running it
09:10 : okay so let's run that
09:14 : um what does it do like a minor research
09:19 : uh yeah so what oh it just completed
09:22 : so after it completed it has reduced the
09:26 : file down to these lines
09:29 : and then now your now you only look at
09:31 : these lines you can probably
09:33 : find it at this point right okay
09:36 : so what does this uh what does this do
09:39 : what does the simplified test case yeah
09:42 : what is the algorithm
09:44 : so the algorithm is implemented in this
09:47 : function which is not that long um
09:51 : it's maybe 50 lines or so
09:54 : yeah maybe 50 lines or so uh the
09:58 : algorithm
09:58 : is basically um oh and also it
10:02 : it it backed it up into an original
10:06 : so it backed it up into the file name
10:09 : dot original
10:10 : so this is the original file and also
10:13 : while it's going
10:15 : if it um the intermediate steps
10:18 : well let me explain the algorithm first
10:21 : so
10:21 : basically it it tries to do the
10:25 : binary search thing that um
10:28 : which is hey cut out half
10:32 : of the file like
10:35 : write down them like just delete the
10:37 : bottom half of the file
10:39 : and then redo the test right um
10:43 : um and and then if if you do that
10:46 : and we do the test and you get the exact
10:48 : same cryptic error
10:50 : then you need you know the bottom half
10:52 : is not needed
10:54 : to generate the cryptic errors and and
10:56 : then you keep going you you subdivide it
10:58 : again
10:59 : um i wanted to make this
11:04 : one problem is sometimes you cut it off
11:07 : at the halfway point and then you end up
11:09 : with invalid syntax
11:12 : right or you break the existing syntax
11:15 : right so uh what you do in that case is
11:19 : if you break the existing syntax like
11:21 : you you cause a syntax error because
11:24 : of your modification um
11:28 : the syntax error should
11:31 : usually be a different syntax error like
11:34 : the signature of your error should be
11:36 : different
11:37 : so that your execute function generates
11:41 : a false
11:42 : which is why i i made this very specific
11:45 : this matcher very specific
11:47 : so that if you if you cause a syntax
11:49 : error
11:51 : that's not this one uh-huh
11:54 : then this execute function actually
11:57 : returns false
11:58 : right right and and therefore
12:01 : if if i cut it off at the halfway point
12:05 : like i i did it here and it's gonna be a
12:08 : syntax error because
12:09 : well you can't have an empty function
12:12 : body like this right
12:14 : that will give you a different syntax
12:16 : error that doesn't match this one
12:19 : and and then in that case what it does
12:21 : is it will
12:22 : undo that operation it'll undo it and
12:25 : it'll try again
12:27 : and then i'm how do i try again i
12:31 : subdivide it even further i i divide it
12:34 : into four pieces next
12:37 : and then i try piece by piece
12:40 : i try each of the four pieces
12:44 : try deleting each of the four pieces i i
12:47 : subdivided
12:48 : uh so basically initially
12:53 : i have the divisor set at two i divide
12:56 : it into two halves and delete
12:58 : and i tried deleting first the top half
13:01 : and then try deleting this
13:03 : bottom half and and see if it gives the
13:06 : same error
13:08 : if it gives it the same error i'm
13:09 : keeping that right
13:11 : but if if it's a different error or
13:13 : different output or no error
13:15 : then i undo that and then i
13:18 : i double the divisor to four and then i
13:21 : try
13:22 : removing each of the four chunks if that
13:24 : still doesn't work
13:25 : i doubled it again into eight and divide
13:29 : uh try removing each of the eight chunks
13:34 : and then if it worked at any point
13:37 : then we're keeping that so
13:40 : so yeah you can see oh problem persists
13:44 : we're keeping that change but if if it's
13:47 : uh
13:49 : if the output changed we're undoing that
13:52 : operation
13:54 : does that make sense yeah that's all
13:57 : this is doing
13:58 : and and the nice thing about this
14:02 : i think is that uh
14:05 : if you were a person doing this
14:07 : intelligently
14:08 : you would definitely be looking at the
14:11 : syntax
14:12 : to prevent from breaking the syntax
14:14 : right you would be like if this is a
14:15 : chunk i'm going to delete this chunk
14:17 : right that's faster
14:20 : and that's a more efficient way to do it
14:23 : if you know
14:25 : if you understand the syntax of the
14:28 : program and i couldn't have done that i
14:30 : could have
14:30 : used a python parser as far as the
14:33 : structure
14:34 : and then just remove like certain syntax
14:38 : node from the tree
14:42 : but this scheme i like it because i it
14:45 : can work for any language
14:47 : it doesn't matter it's slower but
14:51 : it will work for any language doesn't
14:53 : doesn't have to know
14:54 : what uh what language the input file is
14:58 : in
15:00 : so in order to so the the program will
15:04 : return
15:04 : or will complete until you
15:08 : divide it or you remove how many lies
15:11 : and then the the program will have no
15:15 : errors and then you're like okay this is
15:17 : my my lives that i identify i
15:21 : identify that causes the problem is that
15:25 : how you define
15:26 : uh how the program will stop
15:30 : no no no it will it still has an error
15:33 : first of all like at this point it still
15:35 : has an error
15:36 : because the syntax error is still there
15:39 : is that
15:40 : we forgot to close this parenthesis okay
15:43 : so
15:43 : if you remove these two lines then there
15:45 : will be no errors
15:47 : right oh actually
15:50 : the result is not the
15:53 : smallest possible result that it could
15:56 : be
15:57 : and and i could do something to make it
16:01 : absolutely smallest possible result it
16:04 : could be
16:05 : but i i thought this was kind of good
16:07 : enough
16:08 : but basically the stopping condition is
16:12 : when the when the divisor
16:17 : when the number of lines divided by the
16:20 : divisor
16:22 : is less than one then the program stops
16:26 : okay so the divisor is going like
16:31 : like initially you divide it
16:35 : into two halves right the divisor was
16:38 : two
16:38 : and then the number of lines in one of
16:41 : the halves
16:41 : is like 125 probably right
16:45 : right um uh so so and and if that didn't
16:49 : work out it has to undo
16:51 : and then it doubles the divisor to four
16:54 : right and then it doubles the divisor if
16:56 : it doesn't work it doubles the divisor
16:58 : to eight
16:59 : and and so forth so eventually
17:02 : if nothing is working the divisor will
17:05 : be big enough so that
17:07 : the chunk size is one maybe and then
17:10 : it's only removing one line
17:13 : so basically when the divisor becomes
17:16 : really large and it will remove one line
17:18 : at a time
17:20 : and rerun the program each time until
17:24 : or or just the the remaining program has
17:26 : been
17:27 : sufficiently small that even with a
17:29 : small divisor you get a line of one
17:33 : a chunk size of one right like this
17:36 : it has reduced this down to four lines
17:39 : at this point
17:40 : so the divisor only has to be four for
17:44 : for the chunk size to be one uh-huh
17:49 : oh okay so the uh okay
17:52 : and whenever whenever you keep something
17:56 : whenever you succeed in reducing the
17:58 : file
17:59 : you delete this chunk and it you still
18:02 : get the same error
18:03 : right whenever you succeed you reset the
18:06 : divisor back to two
18:08 : right oh okay so the stopping point is
18:12 : actually like
18:12 : after you remove everything else and
18:15 : then you have a very small program
18:17 : that still produce the exact same error
18:20 : exactly exactly okay gotcha so yeah so
18:23 : exactly this program
18:24 : produces the exact same error
18:30 : yeah we see this exact same or not exact
18:33 : same error but this error
18:35 : as based on our matching
18:38 : code here that we define
18:41 : in our execute three function
18:44 : gotcha yeah i think that's really smart
18:48 : so what what would there be a case that
18:51 : this program just not able to find out
18:54 : just not able to build a small program
18:56 : that's producing the same error
18:58 : will that be possible um
19:04 : i guess i can
19:08 : theoretically it can be possible
19:12 : um like
19:15 : i can definitely contrive an example of
19:18 : like
19:20 : like if if the process of um
19:26 : like you can read in the entire file
19:29 : look and and and and
19:32 : detect if the file is exactly that way
19:36 : and if it is exactly that way you spit
19:39 : out this error
19:41 : you spit out this cryptic error you can
19:44 : write a program that does that
19:46 : and then if the program that you're
19:47 : using to test it
19:49 : is doing that then yeah any
19:52 : change you cause to it uh will cause the
19:56 : cryptic error to go away right that's a
19:58 : very contrived example
20:00 : but okay in real life that is usually
20:03 : not the case in real life it's like
20:07 : there's some small thing inside a big
20:09 : file that's causing the problem
20:11 : or a combination of a number of small
20:14 : things
20:14 : inside the file oh
20:18 : gotcha yeah like you can you can think
20:20 : of like a
20:21 : a maybe more intuitive thing
20:24 : is like uh
20:28 : what if you just deleted
20:31 : one line from this file at random
20:35 : and and retested it does it still have
20:38 : the cryptic error
20:39 : right and if
20:42 : if you did that if if it feels
20:45 : may it's maybe pretty likely that you
20:48 : can remove a random line
20:50 : and still have the same error right
20:56 : yeah and you could do that algorithm but
20:59 : that would
20:59 : take a lot longer because there are a
21:01 : lot of lines in this file
21:03 : right yeah i guess as a human
21:07 : like if i do this i will more
21:11 : be like instead of just deleting stuff
21:14 : i will like say just remove a
21:17 : functionality
21:18 : that i know say like this chunk
21:21 : represent this functionality so i will
21:23 : represent this like
21:24 : this block this block this block and
21:26 : then i will test it again
21:28 : but i can't test as fast as this program
21:32 : yeah exactly this this is more brute
21:34 : force and it's dumber than you
21:36 : but it can you can do calculations
21:38 : faster than you can
21:40 : yeah yeah i think that's very cool
21:43 : yeah i definitely see a great value of
21:46 : this especially for the program
21:48 : that it's like a thing that will produce
21:51 : either an error or
21:54 : something because sometimes the bug is
21:56 : not like it's producing an error the bug
21:58 : is
21:59 : the behavior is not what i think it
22:01 : would be like if i do a calculation the
22:03 : calculation is
22:04 : the number that's not i don't expect
22:07 : something like that
22:08 : as long as you can write a matcher that
22:11 : detects that
22:12 : weirdness then this concept can work
22:16 : yeah yeah and
22:20 : for for like web applications which most
22:23 : of us work
22:24 : with um this is still possible
22:27 : but you might need to do something like
22:30 : spin
22:30 : up like a spin up like a
22:34 : headless browser or something to test
22:36 : your webpage
22:37 : like like chrome chrome headless
22:41 : or puppeteer puppeteer is a good tool
22:43 : for this
22:44 : um spin up a headless browser
22:48 : load your web page in there and that is
22:50 : more work
22:51 : and it can put in if you're using
22:53 : typescript or something like that
22:55 : you have to tell typescript to recompile
22:58 : the thing
22:59 : and then wiring it into your existing
23:01 : tool chain
23:02 : might be trouble but
23:05 : but it's definitely doable even even for
23:08 : that
23:09 : yeah the thing is you need to write down
23:11 : your test case
23:12 : using like puppeteer right you need to
23:15 : say hey this is the behavior i want
23:17 : you see i want to see two buttons on the
23:19 : screen but why there's only one
23:21 : yeah yeah yeah that
23:24 : that part of it you know still