Martin's In memory Build System in 140 lines of TypeScript

Captions as YouTube publishes them, usually machine-generated, so names such as Daml and Canton can be misheard.

1. 0:00

   over the last couple of weeks i've uh played around a bit with build systems or um on demand incremental computation computation engines um and i learned a few things along the way i thought it might be interesting to share with you some aha moments and what i'm going to do today is i'll pretty much like walk you through an implementation of a monadic build system and i'll implement that in typescript i

2. 0:33

   assume everybody is like somewhat familiar with that um and i assume also assume i don't need to sell you like to build systems i would assume everybody here kind of like has an understanding why build systems are useful and i don't need to sell you on that is that a correct assumption or is there somebody who needs to be sold okay i guess nobody needs to resolve okay that's correct i don't need to be sold on it it doesn't mean i'm going to use one though okay cool and then let's dive in so

3. 1:13

   build systems are often used for programming language like like to build stuff written in programming languages but you can could do a lot of other things with it as well um and today i don't want to focus on all the programming language aspects of like that they would encounter when using a build system so we have like a very very simple toy programming language and let me jump

4. 1:37

   straight into my editor can everybody see that can everybody like distinguish the different colors yeah okay okay that's great um should i make the font a bit bigger yes please okay perfect cool okay now i have enough space on my screen so as i said we have like a tiny toy programming language and it's not really a programming language um there will be two sorts of file files i need to get focus here um

5. 2:18

   kind of like problem description description so there will be two sorts of files there will be star dot lst files and they contain a list of other files so like a startup lst file could look like uh foo dot dot comma r dot dot that's how like an lst file will look like it's just like a list of files separated by commas and then there are dot files which are just a number like 13 and

6. 2:59

   running an lst file means going into all the listed files getting the number the numbers and adding them that's so that's the programming language um we can add a bunch of numbers but it's very complicated because it's uh spread across files and the interesting part is as i said the build system around this so um what we will do um before i go into how how to implement the build system i will show like show of the api i'm intending to implement so there's already some file in the background

7. 3:47

   um which has the api but full of holes um and i'll show how to use this api to do this so the first thing we need to do let's well they're like well yeah the first thing thing we need to do is we would need to write a spec um and like build systems usually are concerned about like have like a computation graph so we need to spec a graph and let's do that later and assuming we have this graph what we want to do is we kind of like want to tell the build system this file

8. 4:28

   contains this text this file contains that text that's kind of like the things we can tell the build system and then we can go and ask the build system what's the va like what what's the value of this thing so in our in our specific example let's say um let's assume we have like a graph for this back we we still have to write and then we can do things like g set no not get set input and we want to set the input now we want to set like

9. 5:03

   file content so we want to say the file contents of the main.list file are the ones i have above so let's say it's this string and then we want to set the input of another file namely the foo dot dot that is referenced and that number is 13 and then we want to set another in like the other file file contents of bar dot dot and that will be i don't know your favorite number 42 and once we've done that what we do want to

10. 5:42

    do now is we want to ask the build system for a value so for instance we could ask for um get the value for and now we want the evaluate like a list file and we want to evaluate the one called main.list right and we expect this one expected to to print uh what is it 55 okay so that's kind of like the api and then you might go and say oh like one of your inputs has changed so let's say bar file contents bar dot dot is now

11. 6:32

    24. and then if we print the output again we would expect to see um 37 right and what we don't expect when like when we do this we don't expect like the main file to be re-passed or foo dot to be re-passed those should be like they are cached in the in this huge graph we have in memory um which is driven by the build system right and then there are also other things oh i've got a lot of things wrong here i mean there are strings not numbers

12. 7:13

    and then there are other things we want to achieve for instance if i set the input to of bar dot dot to let's say space base 24 space um and then ask what do we get i expect like still the same number but kind of like i expect the build system to stop after it has noticed oh the value hasn't changed right like the file content has changed but the value of parsing the file content hasn't changed so we expect

13. 7:53

    early cut off here um after we've noticed that 24 is 24. okay does all of this make sense so far okay i see people nodding i interpret that as yes cool okay so that's that's like the way we want to use this build system and now we need to spec it um so and the way we're going to do this today is we're going to say there's like there are file contents and file contents are not really there's like nothing computed so they're an input rule and we we just say like the rule to

14. 8:39

    compute them is null so we always need to set them from the outside and then there's another rule which parses a list file parse list and this rule gets two inputs it will get a graph like it will get access to the whole graph but in read-only mode so what we get is like a graph reader and we also get access to let's call it the file which is this like the file which we want to parse or the

15. 9:14

    name of the file which we want to parse and this whole thing will return a list of strings because that's how we intend to um to interpret the contents of a file and what we do then is well we get the contents of the file and then we get them from by asking the build system what is the file content so we ask what are the file contents of the file we care about and we know this is a string and like

16. 9:44

    our like there's like there's some type type holes in our system so we need to tell it explicitly that we're talking about strings here um you can make this like you can make the api of this better but i think that's that's not the interesting part for now so and once we have those contents we say well contents and we split them along with the commas and then we're done so that's just a rule for passing right like usually this is like way more expensive and we would try like we would try to

17. 10:23

    avoid doing this whenever we can um yeah but like here it's cheap but it's just meant to be a proxy okay and then like similarly we have like parsing for that files which takes again let me copy paste so which takes again read access to the graph and the name of a file we get the the contents from the build system and then we take we just turn them into a number oops so we say we return a number and here we

18. 10:59

    do number paris ind and we take content start and we want to like remove useless white space okay and then the last rule we want to do is we want to be able to evaluate list files and that returns a number as well so and they're like two things we do here now first we need to we need to like get the past content of the list file so this will give us like a list of files i don't know list and what we ask here is pass the list file and that gives us

19. 11:45

    a list of strings um and then the next thing we do is we want to have like all the numbers that are in there we get them by mapping over the list and for each item in the list we go and ask the build system what is the value for parse dot of this item and again we need to tell it it's a number and then in the end we take all those numbers and reduce them kind of like we fold over them

20. 12:26

    just using plus x plus y starting from zero okay so this is the specification of our whole build system and as i said like all those functions are very cheap but in general they're very expensive and we want to avoid using them whenever we can okay um any questions so far and by the way if you have any questions at any time please interrupt me okay i don't see any questions okay so now we have like we have used the api next step is to implement this api or

21. 13:06

    something behind this api and we need the graph file for this um all right okay so there are a few things already in here so the first one we've already used is the graph reader and the graph reader gives us a get value function or method and the first argument we've put to this graph reader or like to get value function was usually like one of those uppercase constants and i call them like layers kind of like your graph is layered right there's like the file system layer then there's like the

22. 13:45

    the list parser layer and the data parser layer and then on top we have the devaluation layer so i call them layer and then oh yeah i've called the strings which are file names in our case key so let's call them file here and then we've also seen rules and like a rule is something that takes a reader for the graph and the file string and then computes a value using this using this data so for instance um

23. 14:21

    like this function is a rule right it takes a take the reader of the graph and the file and returns some data and then the graph spec was just an object where for each layer we either gave a rule if it's if it's like a node that needs to be computed or null if it is meant to be an input node right and then we have like finally we have the graph which is the thing that we constructed it takes a spec and gives us an object

24. 14:56

    where we can ask where we have get value so it implements the graph reader interface and we also have set input um to set like values for like fall contents okay let's make this consistent right okay so we need to implement this and this whole thing like as i said we want to do we want to do early cut off so there's like this there will be some notion of when has a file or like has a

25. 15:28

    value been modified so just there's a notion of time and to keep things simple we just say um type time is number we just use numbers for time and whenever we set a value we just advance the time um and then we also need to store like we need to store all the nodes of our graph in in this um in this whole thing so we need a notion of a node um and well they're pretty they're kind of like two things you want to store in a node

26. 16:06

    for in every node first one of them is the value and i said like we don't specify like the exact types for values we just make it uh yeah unknown so you can store whatever you want and you have to cast it when you get it out and we also need to change we also want to to save at what time the note has changed the last time because that determines if we need to rebuild something or not and it will turn out later

27. 16:39

    that for for um for input layers so this node type is enough we don't need to store any additional data but for rule layers we want to store more data so we distinguish like nodes for input layers look slightly different from nodes for um for rule layers so there's something we need to fill in here um which i'll do later okay and then um for convenience we also like we want to we we need to store the layers we get in the spec so they're like

28. 17:18

    an input layer will pretty much just contain the nodes um which are um which is a map from so this string is meant to be a file name and then we store a node so for each input layer we have like we have one of those um and similarly we want to have rule layers which are similar string and then we have like a rule node we also need to store the actual rule for every rule layer so we can actually do something

29. 18:06

    okay so with all these types we can finally find all the fields we need in our class so we need a notion of time let's call this time now and we need um we need to store all our input layers and that is again that's a map from strings to an input layer and this time the string so maybe like it's good string is a file here as well string is a file and here the string is a layer name or layer yeah like a layer name

30. 18:53

    right in other languages i would probably have used a map structure and like which is indexed by a pair kind of like the layer and and the file name but that's almost impossible in javascript at least in my understanding of javascript and then we have rule layers which are very similar so we have a string and a rule layer again the string is layer name okay and now in our constructor we need

31. 19:29

    to initialize all of those and we start with simply with time zero that's good enough and then we walk over our spec so for each layer mentioned ours in our spec we check if the layer is an input layer and how do we well how do we do that we get we get the rule so just as a reminder the spec type is like an object indexed by strings in every value in there is either a rule or null

32. 20:09

    so if our rule is nine we have an input layer and we we just add this input layer to our list of input layers so we say this input layers and we set it at layer and we just said put an empty map in there that's just uh convenient so new map string input layer okay oh and we forgot i forgot to initialize the input layer so this input layer is new map string input layer so we start out with an empty map and here for the nodes we actually want to put the nodes in there so

33. 20:59

    we need an empty map of nodes okay cool and similarly we want to do it like for rule layers we want to do something similar so we say this we will yes and we set at the layer put the rule in and the nodes are an empty map again now i'm under the window the zoom window okay so something is broken here oh i mistyped

34. 22:05

    ah so many typos okay cool so now we have our constructor um right i guess not all of this makes perfect sense yet it will like some parts will just become clear later but are there any questions that are proper road blockers right now okay cool so let's next get to set input oops so what do we want to do what do we need to do when we get a new input um we we need to check if if the the layer we are given is actually an input layer and if it is we need to just set the value

35. 22:55

    in there so um and i don't like i have no intent to make this like really resilient so i just assume we only get input layers so ah actually no so we want to get the notes from the input layers and get layer and we force it okay so now we have like all the all the input nodes for this layer and we might be setting like there might be three things might be happening we might be setting a new input that has never been set

36. 23:39

    before we might be setting something that has already been set to a different value or we might be setting something to exactly the same value and whenever we set something to the same value we want a shortcut right there's no there's no point in recording this if nothing has changed we don't need to do anything so let's distinguish those three cases so first case if the nodes

37. 24:09

    don't have the file we are currently setting that means we actually need to do something and what we need to do is we like we advance the time right like something has changed so we say we increase the time and then we say in the notes we add for the file we add something new um the value is the one we got and change that as the current time um right okay so from now we can assume we already

38. 24:48

    like somebody has already set a value for this file at this layer so let's get the node nodes get file so and then there's this shortcut case i mentioned and that happens if the value we already have in the node is the same as the value we're supposed to set and whenever we do that we can just shortcut and in the other cases we need to again advance the time and we need to change the node so the

39. 25:26

    node value is what the new value and the node change that is now uh this dot now okay so that's that's all we need to do to set a volume is that question okay obviously not so implementing get value is more tricky than that the idea is whenever we ask for a value we can't we need to update nodes across the whole graph so what we're going to do is we're going to implement a helper function which does pretty much all the work and i'll call it

40. 26:12

    update node and it will get layer as its input and it will get a file as its input and it returns the node at this layer like the node at this address or node id so well suppress the warning um and then getting the value at a specific node pretty much just amounts to updating the node at this address and getting its value right so let's walk through what we need to do when we when we need to update a node

41. 27:16

    so if we are asked to update an input node we pretty much need to do nothing we just need to return the node so if input layers has this layer we're referring to um and let's do it might be that this input layer has no node set at this for this file here or no value set for this file right this can happen like you're referring to a file that does not exist for instance so we want we want to catch this case um so let's get the notes at this layer

42. 28:02

    this input layer is get layer and if the nodes do not have the file then we throw an exception um accessing unset value add and then layer let's do it like this that's consistent with what i did in other places a layer file okay and otherwise if we do have the node we just return uh yeah we just return nodes get file and we know the file exists because we've just asked for it value

43. 28:57

    no just a note okay so there's nothing we really need to update for input nodes so if we made it here we know we don't have an input layer which means we have a rule layer so let's get everything that's in the rule in the rule so there's like there's a rule and there are nodes this rule layers get there and we assume yeah we can make the conclusion that if it's not an input layer it's a rule layer and nothing bogus um okay

44. 29:43

    so for rule layers it might happen that it's the very first time we're trying to access a node in the graph nobody has ever evolved tried to evaluate that file at that layer before right that happens for instance at a very at a fresh build like your whole graph is empty so in this case we need to we need to compute grab the value and store it in the graph so if not nodes as file so if we don't have the file we need to recompute it for the first time

45. 30:24

    and how do we do that um we say the value is the rule applied to we need a graph reader well this is a is a graph and in particular a graph reader hands at the file that's how we compute the value for the new um for this node we just need to create however because we want to like in on rebuilds we want to like minimize all the things we have to rebuild so we need to implement some sort of dependency tracking um and kind of like get a hold of like what

46. 31:06

    does calling this root in uh in this in this uh graph at this file like what other calls to get value does it make um and in a language where you have higher order functions you can just intercept all those calls and that is something um we're going to implement next as a helper function so we want something private a private function and i call it get a traced reader and what it returns um is a database uh not a database a

47. 31:45

    graph reader but it also returns a trace and the trace is a list of node ids and we need to define what a node id is a note id is just the address of a note in this whole thing so that's the layer and the file node id that's how we can address a node in the graph so we return a list of node ids how do we do this okay we need to build up a closure so we need a empty we start with an empty trace and now we also need to

48. 32:38

    add a function that we put in the graph reader will return so we want to get value function and get value takes this input a layer and a file and return something unknown and the only thing we do when we call get value in this one first of all we add like what we're trying to get to the trace so we say trace push layer file and then we simply call um kind of like ourselves with the with the layer in the file

49. 33:26

    ah and we want to return no ah and we want this okay so to some extent and then in the end we return both so we return get value and trace so the object you get returned from get traced reader behaves exactly the same as as like as the class instance we currently have but in addition to that it also tells you all the calls to get value that have happened um so yeah that's yeah it's tracing

50. 34:05

    the calls to get value so and our plan is to use this whenever we apply the rule to track the dependencies so what we need to do as well for rule notes i said we need to add a bit more and one thing we want to add are the dependencies we've tracked they will become interesting later and we also um in order to be able to do early cutoff we also need to store at what time we've last updated this note this will come apparent

51. 34:45

    a bit later why but i think it makes sense to edit now right okay so that's instead of calling rule with this we want to use a trace reader here so let's get a reader oh no wait let's get a reader using this get traced reader and then we use the reader instead of this and now we create a new node and we have a rule node and the node will contain a value well that's the way we just compute it it will have a time when it was last changed that is

52. 35:32

    now it will have dependencies and the dependencies are exactly what the reader has trade like the trace reader has traced for us those are all the dependency trace and then we have this timestamp for updated add and that's now because we've just changed this like we've we've updated the node okay and we need to add this whole thing into the notes of this layer so notes set file node and we need to return the node

53. 36:16

    so that's the case of adding a fresh node cool so now we know we're in a situation where the note has already been evaluated before so it's not the first time and we want to do a few things to do um to do early cutoffs the most like i guess the most obvious one is like checking if the dependencies have changed or not if the dependencies have not changed we know the value has cannot have changed well i'm i'm working under the assumption

54. 36:55

    that all our rules are pure maybe i should have said that earlier but i think that's how build systems work um so i think that's like a very obvious cutoff there's another cut off like we might we might run into the same notes multiple times during one build and there's pretty much no point in doing anything after the first time that is what this updated ad is for like it tracks the last time

55. 37:28

    we we called note update update note updated add so the shortcut we want to add is if the node oh wait first of all we need to get the current node so node is nodes get file so if the node has been updated at time now that means you already know it's up to date and we don't need to do anything so we can just return the note and be done and the next thing is uh dependency tr checking the dependencies so what we want to find out is uh have the

56. 38:21

    dependencies changed and that's a boolean and for now we assume they have not changed and then we run over all the dependencies and check so for um step in now off so for all the dependencies of the node we check if we like we update the dependency node this update node at dab dot air dab dot file and if we find out the last time it has changed was after we looked the last time at the current node so the the dependency has been has changed

57. 39:17

    after we've we've updated this node the last time that means like the dependency has changed right and like one of the dependencies is uh done as out of date so no not now i mean note updated ad and that is the case we need to we say dependencies changed is true and we can stop looking through dependencies what is wrong here oh okay so that is early cut off okay so now if the dependencies have not changed we know the value has not changed and we

58. 40:16

    can just return but before we return we want to say we've actually we want to record that we've actually just updated the node so this node is up to date right we know its value is up to date because none of its dependencies have changed so we say we have just updated it now and then we can return the node cool okay so next thing we know is the one of the dependencies have changed and that means we need to re-evaluate the node and we do that pretty much the same way

59. 40:53

    we do it up here you construct a new reader a trace reader and then get the value and now there's another thing we can optimize it like sometimes it happens that the inputs have changed but the value has not changed right for instance like in our addition thing i don't know like before your inputs were 3 and 5 and the sum is eight no they're four and four and the sum is still eight so kind of like you don't need like you can you don't need to update

60. 41:26

    the time and what you've changed because like your your consumers for your consumers it looks like nothing has happened so that means we only need to update when we have changed the last time if we have actually changed so no value if that value is not the same as the new value we've just computed then we say um this the value is the new value and we also say we've just changed now okay and regardless of whether we have

61. 42:11

    changed or not we need to update our dependencies right like our dependencies could have changed without our value actually changing um i don't know for instance we could have replaced one file containing five by another file containing five um but for the sake of like future dependency checks you want to look at the new dependencies not at the old dependencies um so we say no dependencies is

62. 42:40

    the trace we get from the reader and then we want to also say that we've just called update let's start now and once we have that done we can return the node okay that's it that's the whole implementation um let's see it in action so let's open the terminal right and let's call yarn demo and demo we'll call the thing we've described up here so what we expect is 55 37 37 let's see if that happens i guess we crash

63. 43:27

    no we didn't okay cool so that means all the re-evaluations um have happened in the way we intended um i guess what we don't what we can't really see here is like what computations have actually happened right i could just like reevaluate everything all the time and you wouldn't see um so to convince you that we're doing the right thing let's add a bit more logs so let's log here um that we've updated

64. 44:05

    we've called parse list on file and here we've called pars dot on file here we've called parse no we've called evil list on file okay now we have a lot more things to see and let's run it okay and this is annoying to do which makes no sense anymore cool so first run what we're doing is recalling parts list on the main list and we're calling parse dot on both files and then we call evaluate well we need to touch everything because it's a fresh build so that's fine

65. 44:59

    um next what happens next if is we've changed the value of bar dot to 24 and we ask again what's the value and we see we only parse that like we only pass bar dot dot and then evaluate we don't parse the old file anymore that we don't parse food dot and we don't parse the list so that's cool next we change the value of bar dot to 24 with a few spaces around and we see the only function we call is power start and then we see oh

66. 45:36

    the value is the same so we can stop and we know all other nodes are up to date and maybe one last thing is if we don't do anything and just call again we expect to print 37 and no more outputs see if that works yes 37 again and no calls to function functions in the middle okay cool that is a monetic build system implemented in 139 lines of typescript