Time Traveling Debugger for Python

I started working on a time-traveling debugger for Python. This a video documenting it.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : um can i show you something uh
00:03 : i'm working on basically uh the
00:07 : the time traveling debugger for python
00:11 : that's what i'm working on and
00:15 : i'll show you an example of what i got
00:17 : so far
00:19 : uh oh i i was starting the work on
00:22 : storing it in a sequel light database
00:24 : but
00:25 : i haven't finished that part um
00:31 : but let's let's take whoops
00:36 : um am i in the c price
00:39 : on project yeah i'm going to see so
00:42 : python
00:43 : is python has
00:46 : a compiler and an interpreter
00:49 : uh both of them are written in c
00:52 : and and and in the last week or so i've
00:56 : really dug into
00:58 : the source code of python and
01:02 : and i'm able to build python i type
01:05 : make here and it'll build the c files
01:08 : etc and now i have a
01:11 : python executable it's called python.exe
01:15 : even though i'm on mac uh they call it
01:19 : python.exe
01:20 : which is weird um and i
01:23 : have some test scripts
01:26 : um let's do this
01:30 : permutations
01:35 : so okay i'm gonna show you one of the
01:38 : programs
01:42 : that i have as test programs so this is
01:44 : a test program
01:45 : okay all right
01:48 : and uh this is a problem that i
01:52 : solved for a leadcode.com code challenge
01:56 : and i just i just took that and put it
01:59 : in here as one of the test programs
02:01 : um and i basically hacked the code
02:05 : i added a rewind module
02:11 : yeah i think i'm calling this
02:15 : rewind as in it's able to rewind your
02:19 : code
02:21 : i added this module with a bunch of
02:25 : functions
02:26 : that are called whenever specific things
02:29 : in the interpreter happen
02:32 : and then the interpreter code is in this
02:35 : file called
02:36 : c eval dot c and this file is
02:39 : where python is actually
02:43 : executing the instructions line by line
02:46 : um okay it is executing something called
02:49 : bytecode and the way it works is
02:53 : you you take some python code
02:57 : i'll call it that pi something dot pi
03:02 : uh it goes to the compiler
03:07 : i'm gonna use different shapes
03:13 : okay something that pi goes to the
03:15 : python compiler you don't think of
03:17 : python as a compiler because you think
03:19 : of it as a
03:21 : interpreter usually but the reason it's
03:24 : called
03:25 : the reason there's a compiler is because
03:27 : there's a process to first take your
03:29 : source code
03:30 : and generate bytecode
03:34 : generate python python bytecode
03:38 : which i'm going to call pyc
03:41 : python python compiled code
03:45 : and that compiled code is in a binary
03:47 : format it's
03:48 : difficult to read if you try to open up
03:50 : the file
03:52 : but but it's basically a
03:57 : to give you an intuition is like if if
03:59 : you have a
04:00 : compound statement that's like
04:09 : let's say you had a statement like this
04:12 : then the buy code for that would be
04:15 : something like
04:17 : you know load
04:20 : load b
04:24 : load c add
04:30 : and then and then load
04:34 : d and then add
04:38 : and then store it into a so
04:41 : so by code looks like this basically
04:44 : where
04:45 : even if you have a compound statement
04:48 : it breaks it down into the individual
04:51 : operations that would have to happen
04:54 : so and each individual operation
04:59 : you know is is like uh it's atomic
05:02 : operation there's
05:03 : there's no no compound even though you
05:06 : can do a lot in a one-liner
05:08 : when it's converted to buy code it's the
05:11 : individual
05:12 : direction each instruction just
05:16 : does one thing so is this code directly
05:20 : like readable by the machine
05:22 : or like no no this is like um
05:26 : this is a specific um
05:30 : instruction set that python defined
05:32 : specifically for python
05:34 : um so um
05:38 : so this is not a real machine code
05:41 : even though this look in in terms of
05:44 : flavor
05:44 : it looks a little bit like machine code
05:46 : but it's not real machine code
05:49 : gotcha which is why we call it the
05:51 : python compile code and then
05:54 : and then um that goes to the interpreter
06:00 : that goes to the python interpreter and
06:04 : and then you know out comes the result
06:07 : yeah
06:07 : whether you print stuff out to the
06:10 : terminal or
06:11 : you have a web application or whatever
06:13 : you know
06:14 : that depends on what the code actually
06:16 : does in in in this compiled code
06:19 : so um so anyway this
06:22 : c eval.c file here
06:26 : is is this is the interpreter this this
06:29 : is the interpreter so i have
06:31 : i hacked into the interpreter well while
06:34 : it's
06:34 : going through each of the instructions
06:37 : and i wanted to
06:38 : intercept i want to intercept
06:42 : everything that python is doing
06:45 : basically
06:46 : as as it's doing
06:50 : okay so how did you get the interpreter
06:52 : code
06:53 : i downloaded from their github
06:57 : so so python python
07:04 : uh it's it's this one it's python
07:07 : slash see python that okay
07:11 : that's where their code is and so so i
07:14 : get cloned it and then here i have their
07:17 : interpreter code
07:18 : and i it took some digging
07:22 : and also asking the irc channel
07:25 : where where there's people that talk
07:27 : about python there
07:29 : i could go and ask questions i would
07:32 : have to say
07:33 : python is pretty well documented
07:37 : um it is still difficult to learn it
07:40 : because there's just a lot there but
07:43 : it's quite well documented like it has
07:45 : these paragraphs here that you can read
07:49 : and it also has links to other articles
07:51 : that you can read
07:55 : but anyway so
08:00 : so this is where the individual
08:02 : instructions
08:03 : actually happen there's a huge
08:07 : switch statement and each target
08:10 : each one of this target and then this
08:13 : name
08:14 : that's the name of a type of bytecode
08:16 : instruction
08:18 : no no app means there's nothing to do
08:21 : it's a skip
08:23 : load load fast means load a local
08:26 : variable
08:27 : there's a slow version of load but uh
08:30 : loading local variables is fast and then
08:34 : load cons that's like a cons like a
08:36 : number or
08:37 : something that you're loading um anyway
08:40 : so so i can
08:41 : just see every instruction that
08:45 : python does i added this line here
08:49 : which which i call log up i'm logging
08:52 : this operation
08:54 : okay so i'm logging all the things that
08:57 : python is doing
08:58 : and in addition i also do
09:03 : for specific things
09:07 : i i have an extra log statement like
09:10 : like uh
09:12 : like list append i i want to
09:15 : intercept that in a specific way so so i
09:18 : have
09:19 : i added my rewind anything you see that
09:22 : starts with rewind that's my
09:24 : module right and so whenever
09:28 : there's a list append instruction
09:31 : i log that specifically and also for the
09:35 : set ad
09:37 : uh there's a bunch of stuff the store
09:40 : subscript is something like like
09:43 : i have a dictionary and then
09:47 : and then i do something like this i'm
09:49 : storing a thing
09:50 : via a subscript notation so this is
09:53 : store subscript so whenever you do this
09:56 : in your program
09:57 : it goes to here and then i log that as
10:00 : well
10:00 : so so basically i am intercepting all of
10:04 : these things
10:05 : that uh python does and and i'm
10:08 : logging it to a file so so i just
10:12 : i just uh no i just ran this program
10:15 : right
10:15 : so by running this program it's going to
10:17 : log this file which i call it rewind.log
10:23 : and it prints out this stuff
10:26 : okay what are the numbers like
10:29 : number 76 what is that these are line
10:32 : numbers
10:34 : but this is not this is
10:38 : some code in python internals so i'm
10:40 : going to skip this part
10:43 : the part that starts being our code is
10:47 : here
10:48 : uh here that's that's the file that i
10:52 : actually executed this one right
10:55 : and uh so i intercepted push frame
10:59 : which is whenever a function is called i
11:02 : push a frame onto the stack
11:04 : so i i intercepted that so i print that
11:07 : out into this file whenever that happens
11:10 : and okay and here we are pushing frame
11:14 : where the source file is our
11:17 : permutations to
11:18 : source file so here right and
11:21 : let me do this side by side
11:32 : um okay so here is
11:35 : this is line one it's over here
11:39 : and we're pushing a frame because when
11:41 : you declare a class
11:43 : you push a frame and then and then
11:46 : inside the class
11:49 : uh well here it's doing some stuff
11:53 : to declare this class i believe yeah
11:55 : it's saying
11:57 : i'm i'm gonna make a string whose value
12:00 : is solution
12:01 : and i'm gonna store the qualified
12:05 : name of this class to be this string
12:09 : and this string has this id
12:12 : so so this star star id is referencing
12:15 : this string that has solution in it
12:19 : so is this co so basically intercept
12:22 : uh in the ce valve
12:25 : [Music]
12:26 : and then whatever the class you you have
12:29 : a class
12:30 : you declare a class like all these just
12:33 : happen
12:34 : because you probably have intercept code
12:37 : of say like
12:38 : um
12:41 : yeah i i because i see all the
12:44 : actually let me uncomment
12:48 : one thing in my code and that will give
12:51 : you even more
12:53 : uh output in this file so i just
12:57 : i'm gonna make i
13:00 : uncommented these two lines which give
13:03 : additional output
13:04 : so i'm recompiling python and then i'll
13:08 : run it again
13:12 : that way you can see even more of what's
13:15 : going on
13:32 : so
13:35 : wow it's taking a while this time okay
13:39 : what did i change
13:46 : okay done okay so all right so
13:50 : now my rewind.log has a lot more stuff
13:53 : in it
13:54 : uh i i put i put these
13:57 : dash dash to mean like this is
14:01 : comments sort of like this is additional
14:04 : information in in addition to the
14:06 : stuff i really want to spit out uh
14:10 : there's a python the the python
14:12 : interpreter has a stack
14:16 : um although this stack is not totally
14:19 : the same as the call stack
14:21 : it's it's like the ver the the value
14:23 : stack
14:24 : oh the the instructions like add
14:27 : or even call a function are based on
14:30 : what values are on the stack right now
14:33 : um okay but uh let's go to this
14:37 : file i'm just gonna let's just skip to
14:39 : line 21
14:40 : here in in this file so i'm going to
14:43 : search for pound
14:45 : 21 so okay
14:49 : um so this is store name
14:52 : permute unique that basically means it
14:55 : has
14:57 : created this function and it's gonna
15:00 : here it says new object function here
15:02 : that means it's created this new
15:04 : function
15:05 : or it's my my login system has
15:08 : registered that the system created this
15:12 : function and we're storing that into the
15:14 : name
15:15 : permute unique which is what happens
15:18 : when you define a function
15:20 : right you store a function into some
15:22 : variable name
15:23 : so that that happens here and then we
15:26 : visit
15:27 : line 21 over here
15:30 : okay so let's try to follow what's going
15:32 : to happen
15:33 : so line 21 is we're gonna
15:35 : [Music]
15:38 : we're gonna uh let's see
15:43 : we're actually calling a function here
15:45 : so there's a call function
15:48 : instruction there's a load name first
15:51 : it's probably just to load the name
15:53 : solution here because
15:56 : when it when you call a function you
15:58 : name the function by name so it loads
16:00 : the name of the function
16:01 : and then it actually calls this function
16:04 : and then when it calls the function
16:08 : this this class doesn't have an
16:11 : constructor so we don't have to call the
16:13 : constructor actually
16:15 : so there's no additional stuff here
16:18 : and then it just we just end up with a
16:21 : new
16:21 : object of type solution and then we
16:24 : store it in this
16:25 : s variable here okay
16:28 : so that's line that's line 21 and then
16:31 : we move on to line 22.
16:34 : uh here we're gonna
16:37 : uh load this method
16:40 : uh and we we've and then my system has
16:43 : picked up that
16:45 : there's this new list that we created
16:48 : this new list
16:49 : with a one two three in it so my logging
16:52 : system picked up oh
16:53 : there's a new list and the way python
16:57 : sometimes instantiates a list is first
16:59 : create a new empty list
17:01 : and then we'll it'll extend the list
17:03 : with these
17:04 : uh literal values in it so we first get
17:07 : a new list
17:08 : and then get a list extend with the one
17:11 : two three into the list
17:13 : that's pretty easy like basically like
17:16 : walking through the code just by reading
17:18 : the
17:20 : yeah just by reading this log or
17:22 : basically you are tracing
17:24 : what the interpreter is doing step by
17:26 : step
17:27 : and and then we push frame and and
17:29 : that's the call into this method now
17:31 : when we when we push
17:32 : frame uh so there's a name
17:36 : of the function that's being called
17:38 : which is this permeable unique method
17:41 : right and then let's go now
17:44 : now we visit line number three so let's
17:46 : go to line number three line number
17:48 : three is this
17:50 : line which makes sense because we just
17:52 : called that method
17:54 : and then now it's gonna call this
17:55 : function uh
17:57 : so we are uh let's see
18:01 : we again we picked up there's a new list
18:03 : being created that's probably
18:05 : this this one here yep
18:08 : and then we
18:09 : [Music]
18:12 : uh this load global load fast
18:15 : oh we call this built-in function sorted
18:19 : there there it is we're sorting these
18:21 : numbers
18:22 : so we call this built-in function called
18:24 : sorted
18:26 : my logging isn't so stuff
18:29 : or the new link like live 5 69
18:33 : until call sorted what what are those
18:37 : stuff
18:39 : uh what's sorted no like
18:43 : like so this line number three
18:46 : are um to call permute unique
18:50 : with two variables one is the empty list
18:54 : and one is whatever the result you call
18:56 : sorted
18:57 : yep so like on the right hand side
19:01 : you have the rewind and the line between
19:07 : you broke off hello
19:13 : hello i can't hear you anymore
19:24 : hello oh
19:35 : i'm not hearing you anymore
19:37 : [Music]
19:39 : um what can we try here
19:50 : oh
19:52 : wait oh
19:59 : sorry one second it might be a problem
20:02 : on my end
20:08 : one second
20:18 : can you do one
20:43 : can you hear me
20:52 : [Music]
20:58 : [Music]
21:00 : yeah okay
21:03 : we're back sorry about that okay
21:08 : let's continue um
21:12 : so so these two guys get called
21:15 : and then your question
21:18 : was what
21:21 : are these disguises
21:26 : uh live 75
21:30 : on the on the on the right hand side
21:32 : there are a few
21:34 : lines between like create a new list
21:39 : and a call building function right if
21:42 : you scroll up a little bit
21:43 : yeah oh oh oh yeah yeah what are these
21:46 : doing here
21:49 : okay um i think this load
21:53 : global again it's just load this global
21:56 : variable
21:56 : which is this sorted function and then
22:00 : load fast is
22:04 : it's just loading this nums variable
22:06 : loading its value
22:07 : onto the stack oh and by the way this
22:10 : stack
22:12 : i should talk about this stack this is
22:14 : like the working stack
22:15 : of the interpreter and i just print it
22:18 : out here
22:19 : so at the moment the stack has
22:22 : a list and this function on it
22:27 : and this function is called permute
22:31 : unique so we're playing we're planning
22:34 : to call this function
22:35 : on on line six over here i think
22:39 : and then when we load the global you can
22:42 : see after loading
22:43 : the global the stack now has this
22:46 : built-in function or method called
22:47 : sorted so the
22:49 : purpose of the load is just to load the
22:52 : actual function in by
22:54 : the name of the function
22:57 : and then load fast here is to just
23:01 : load the value of nums into the stack
23:05 : so we have the name nums we're just
23:08 : loading it onto the stack and now
23:10 : after that the stack has this list
23:12 : object on it
23:14 : okay and then and then now we're ready
23:17 : to call this
23:17 : sorted function so we we call that
23:21 : and the reason we had this permeable
23:23 : unique function
23:24 : loaded onto the stack is because we
23:27 : loaded global
23:28 : for the name of the function initially
23:31 : so we first load the function onto the
23:33 : stack
23:34 : and then we need to prepare all the
23:36 : arguments of this
23:38 : of the function and also load them onto
23:40 : the stack the stack
23:42 : but because understand what are the
23:45 : stuff that you're currently working with
23:48 : yeah yeah in this it's a function and a
23:50 : bunch of arguments
23:51 : okay yeah so so yep the stack is how it
23:56 : remembers
23:57 : its place so after loading this
24:00 : permeable unique function onto the stack
24:02 : and then it's preparing the arguments
24:04 : it's gonna pass to the function which
24:06 : are
24:07 : first this empty list so we did this new
24:10 : list
24:10 : thing and and now this is the new empty
24:13 : list
24:13 : it put that onto the stack and then to
24:17 : prepare the next argument to the
24:19 : function it actually has to load another
24:21 : function
24:21 : and call it right so that's what so
24:24 : that's what it was doing
24:26 : loaded the sorted function and then it
24:29 : also had to load this
24:30 : list which is the argument that goes
24:33 : into sorted
24:34 : so it did that and then i called sorted
24:38 : and then as a result of calling sorted
24:40 : it's got
24:41 : another list uh that's in the stack now
24:45 : that um
24:46 : that's the result of whatever sorted
24:49 : returned
24:51 : and and then now and then now we finally
24:53 : push frame
24:55 : to call this permeate unique function
24:57 : and then we keep going and now we're on
24:58 : line
24:59 : seven now
25:02 : yep so uh
25:05 : yeah so so well let's not well
25:08 : there's a lot of content here so we're
25:11 : only
25:12 : about like one fifth all the way
25:15 : through this the execution of this
25:17 : program but
25:18 : and and this i don't well this is gonna
25:22 : find all unique permutations of the
25:24 : numbers one two and three
25:26 : so it's gonna keep looping here for a
25:28 : while
25:29 : uh but but essentially
25:32 : it my goal here
25:36 : is to track everything that happens in
25:39 : the program to
25:40 : enough detail that i can write another
25:44 : program
25:44 : that reads in this log and reconstruct
25:48 : all of the previous states of the
25:51 : program
25:55 : yep yeah so so that is the goal and i i
25:58 : feel like i'm pretty close
26:00 : here um and it's
26:03 : pretty exciting uh so yeah so the next
26:06 : step is i'm gonna write a program to
26:09 : go in through this lock parse it
26:12 : and then i'm gonna recreate all of the
26:16 : objects like whereas in
26:19 : in my previous time
26:23 : time travel debugger code
26:26 : i i actually had the programming
26:29 : language
26:30 : itself be
26:33 : immutable right but i had
26:37 : like when like i built my own
26:39 : programming language and in the language
26:42 : when it's running all the data
26:44 : structures are immutable
26:46 : well it was pretty impractical to make
26:49 : python do that
26:52 : so so and i kind of changed my mind
26:56 : about that
26:57 : because i do want it to work for
26:59 : [Music]
27:01 : you know the mainstream programming
27:02 : languages and that's not going to be
27:04 : practical to change
27:06 : a mainstream language to do that
27:10 : so i'm just going to have it log and
27:12 : then i
27:13 : reconstruct all the path state based on
27:16 : the log
27:20 : reject the past date okay so
27:24 : you have the log and then you create you
27:27 : put on the log
27:29 : you are going to
27:33 : write a program to parse the log and
27:35 : then
27:36 : um you are going to create
27:40 : say the object on the log
27:43 : at that time that's gonna be immutable
27:45 : right
27:47 : uh yeah when yeah i think i'm gonna
27:50 : recreate all
27:53 : historical states by using immutable
27:56 : data structures
27:58 : um okay so so it'll be something like
28:02 : um yeah i'll put our
28:06 : picture on the side here it'll be
28:09 : something like
28:13 : this is by the way i i was inspired to
28:17 : do this
28:19 : after i learned about something called
28:21 : operational
28:23 : transform um which is a technique
28:27 : that's used by collaborative editing
28:31 : systems
28:31 : such as google docs
28:35 : so you can google docs you know have
28:38 : multiple people editing the same
28:39 : document at the same time
28:41 : and but but but each
28:45 : each user has
28:48 : their own current version of the
28:50 : document right
28:52 : like okay i i don't have that problem
28:56 : here
28:56 : that i just like uh so
28:59 : you have like a google server and
29:02 : and then like there's two users editing
29:06 : a google doc right
29:07 : so when when a user edits a google doc
29:11 : what google doc does is it uses
29:14 : something called
29:15 : ot which is short for operational
29:24 : transform
29:26 : and what it does is actually when you
29:28 : add
29:29 : add some text
29:32 : this this is
29:36 : this is captured as a command that
29:40 : that gets executed on the document
29:42 : basically
29:44 : and then that that command gets sent to
29:46 : the server
29:47 : oh that i meant for this to be server
29:51 : that command gets sent to the server and
29:53 : it gets blasted to
29:55 : the other client so the other client is
29:57 : like
29:58 : oh i got a command that says at hello
30:02 : here at this position but
30:05 : but if that if this client at the same
30:08 : time
30:09 : had a conflicting command like
30:12 : the the user also wanted to add
30:15 : hi here right uh what that does
30:19 : is there's a transformation if the two
30:23 : commands
30:23 : happen to be conflicting there's a
30:26 : transformation
30:28 : procedure that will transform
30:31 : this at high in a way that
30:36 : uh works with this at
30:39 : hello command okay um
30:46 : how how should i describe so it will be
30:49 : like
30:50 : okay the server told me i have to
30:53 : add this hello but because the
30:57 : ad hello has higher has a
31:00 : higher precedence than my add high
31:04 : then i need to add high after the hello
31:08 : so
31:09 : so what i'm gonna do is sort of
31:13 : after this at hello i'm gonna put
31:16 : my ad high after the hello
31:21 : and and what that means is i'm gonna
31:24 : shift the index
31:25 : of the insertion over by five
31:29 : to to make the high go after the hello
31:32 : oh so so if there's some intelligence in
31:36 : the algorithm
31:37 : to to sort of resolve these conflicts
31:40 : uh automatically by saying well if the
31:43 : hello takes higher precedence than the
31:46 : high
31:46 : then i can i should shift the high over
31:49 : to after the hello has been inserted
31:53 : so it's kind of like a queue right you
31:56 : have different
31:57 : common uh like uh different
32:00 : like uh commands coming from the server
32:04 : and then you put them in and then you
32:07 : also put your local
32:09 : in the queue as well and then there is a
32:11 : certain
32:13 : um algorithm that's like uh
32:16 : okay the two things
32:19 : are uh at the same time then i do this
32:22 : to resolve the conflict yeah but but the
32:26 : the conflict doesn't have to be solved
32:28 : at the server
32:30 : the conflict can be resolved at each
32:32 : client
32:33 : computer right the server here the
32:36 : server just
32:37 : each event and then the the
32:40 : client can take the event and do
32:42 : whatever yeah
32:43 : yeah so so but i i like i don't have
32:47 : that problem
32:48 : in my scenario because i don't have
32:50 : multiple users
32:51 : of my same runtime but what i took away
32:54 : from
32:55 : that is that you know i i don't have to
32:58 : do this immutable data structure
33:00 : during runtime i can just reconstruct it
33:03 : and look at
33:04 : each operation that the python
33:08 : interpreter does
33:09 : as a command and then based on that
33:12 : command i will
33:13 : transform the state in a certain way
33:16 : right
33:17 : so for example if i have this you know
33:23 : if i have this push stack
33:27 : wait where's the push stack
33:31 : it uh push frame i mean if i have a push
33:34 : frame
33:34 : that means i'm gonna make like initially
33:37 : i'm gonna have an
33:38 : empty stack in in my stack initially
33:42 : that's empty
33:44 : but if i have a push frame i can
33:47 : interpret that as
33:49 : i have a push frame command that's
33:52 : coming in
33:53 : and then and then i'm therefore
33:57 : i'm gonna have a frame on on my stack
34:00 : now
34:01 : but but i can perform this in an
34:03 : immutable way
34:05 : if i right um
34:08 : so so i'm basically yeah so basically
34:10 : i'm gonna re
34:11 : rebuild all the other immuno structures
34:15 : that i would have had if the language
34:17 : was immutable in the first place
34:19 : and then as i go i'm gonna store each
34:22 : one of these immutable
34:23 : data structures into the database the
34:26 : way the same way that i did before
34:29 : and then my zoom debugger can work off
34:32 : of that
34:32 : and and display this zoom interface and
34:36 : everything
34:40 : yep that that's the plan i just want to
34:44 : tell you about that yeah
34:47 : yeah that's yeah
34:50 : when uh the stuff can work with like
34:52 : real language so that
34:54 : you can test it in like a
34:57 : program that's written in like the
34:59 : mainstream language i think that's
35:00 : really
35:01 : really nice yeah yeah i hope that works
35:06 : i hope that