Odin Intro (3 / 3) - Code Examples

This is a follow-up to two prior videos that introduce the Odin programming language. In this video, I'm going to walk through several small examples of Odin code, though we won't be focusing on the details of the specific problems and solutions. Rather, we'll just focus on the aspects of the samples that are unique to Odin. Most of the Odin features in this code were covered in the prior two videos, but we'll also encounter a few things not yet covered. The code samples are all taken from the Exercism project, which is a collection of programming practice problems for many various languages, including now Odin. So, here first is a procedure implementing binary search. The procedure named find takes a slice and a target value, then returns the index of the target value within the slice, plus a boolean indicating whether the value was found or not. As usual for a binary search, the input list is assumed to be sorted, and the target value, if present, is assumed to occur only once in the list. In the body, we first declare two variables, a start index initialized to zero, and an end index initialized to the length of the list. We then loop for as long as start is less than end, and each iteration we get the midpoint between start and end, check if the value there is equal to the target, and if so, return the midpoint index and true. Otherwise, we adjust the end or start index depending on whether the midpoint value is greater than or less than the target. If the target value is not present, the start index eventually equals or exceeds the end index, ending the loop, and then we return zero and false. All of that should be familiar to you if you've ever implemented a binary search before. Anyway, the first Odin feature to note here is the optional okay directive after the return type. This directive allows calls to the procedure to ignore the last boolean return type. Normally, when we call a procedure, if we use the return values, we have to have an assignment target for them all. So, here the call to find has two assignment targets. We can always use underscore to discard any your values we don't need, but thanks to the optional okay directive here, we can also call the procedure as if it just returns an int, making this last call valid. The reason Odin has this feature is mainly because a number of common base library procedures return a boolean as indicator of success, and often this boolean can be safely ignored, hence this convenience. The other interesting Odin feature here is the use of the type parameter dollar sign T. Note that the dollar sign prefix must only be put on the first occurrence of a type parameter in the parameter list, so only the first T here has the dollar sign. What the parameter list here indicates is that the first argument must be a slice, but can be a slice of any kind of element, and then the second argument must match the type of the slice elements. So, say if the first argument to a call is a slice of ints, then the second argument in that call must be an int. Likewise, if the first argument to a call is a slice of strings, then the second argument in that call must be a string. However, keep in mind that the procedure must be compiled separately for each call with a different type for T, and the procedure may not necessarily compile for all types of T. In this case, the target value is used in a less than operation, so T must be a numeric type to be accepted by the compiler. If we call the procedure with, say, a slice of booleans, then that call will be rejected by the compiler. Here we see some tests for the binary search procedure. The standard testing API is imported as core testing, and then each test is defined as a procedure having the test attribute and a single parameter of type pointer to testing.t, which be clear is a struct type defined in the testing package, not a type parameter, despite the choice of name. In a test procedure, we can call various procedures from the testing package, such as expect value, which logs a test error if its second and third arguments are not equal. Note that expect value, like most procedures of the testing API, takes the testing.t pointer as first argument. The second code example is a procedure that returns true if the provided string is a pangram, meaning a string that contains every letter of the alphabet. The solution is case-insensitive and ignores characters that aren't letters of the English alphabet. In the procedure, we use an Odin data type called a bit set. Here we define a type alphabet to be a bit set that encompasses the range of characters from lowercase A to lowercase Z, meaning each alphabet value has a bit for every character in this range. Because there are 26 letters in this range, an alphabet value must be at least 26 bits in size and so must occupy at least 4 bytes. In many cases, Odin will round up the size of a bit set for the sake of alignment. Be clear that Odin considers bit sets with different ranges of values to be completely separate types. For example, if we created a bit set musical notes with the range of characters A through G, that would be a separate type with a different size. Anyway, after defining the alphabet type, we then create an alphabet variable expected, which will represent the set of letters we expect to find in the string. By the way, the zero value of a bit set is empty, meaning all the bits are unset. We then assign the variable an alphabet literal containing every character of the alphabet set, the full lowercase alphabet. In the next assignment though, we demonstrate a more convenient way to get the same result. We simply negate the empty set with the tilde operator. Anyway, we'll then define a constant we'll need representing the difference between ASCII lowercase A and ASCII uppercase A, which should be 97 - 65 equaling 32. Next, before looping through the characters of the string, we declare another alphabet variable found, which will track the letters we find in the string. And we leave it uninitialized so it defaults to the zero value, meaning an empty set. The for in loop will assign each rune of the string to variable r. Remember, a rune is an unsigned integer representing a Unicode code point. And then, when we add two bitset values together, that returns the union of the two sets. So, here we can add a value to the found set by adding it together with a set containing just the individual rune. If the character is lowercase, we add the rune as is, but if it's uppercase, we add the upper to lower diff to get its lowercase equivalent. Lastly, after the loop, we return the equality test of the found and expected sets. If the string has every letter of the English alphabet, then found and expected should match, so the procedure will return true. Looking at the tests for this procedure, the only new thing here is that the tests use the expect procedure, whereas expect value logs an error if two values don't match, expect logs an error if its boolean argument is false. The next sample implements a procedure reverse that reverses the characters of a string. To work correctly with a broad range of Unicode characters, we use a procedure from the Unicode UTF-8 package called decode grapheme clusters. A grapheme represents what a user perceives as an individual character. For some characters in complex writing systems, a single grapheme may be represented by a cluster of code points rather than just a single code point. So, this procedure returns a dynamic array of graphemes plus three other values, which we don't need here, so we just discard. Because the returned dynamic array is allocated, we should eventually free it, so we defer a call that will delete the array. Because the call is deferred, it won't execute until execution returns from the procedure. To make a new string from pieces to build it up incrementally, we'll need a string builder, so we create one by calling builder make from the strings package. This call also allocates, but we don't delete it because we're going to return the string built by the string builder, and then it will be the caller's responsibility to ultimately deallocate. Next, we then use a foreign loop to iterate over the graphemes, but in reverse order as denoted by the reverse directive. Inside the loop, each grapheme will be assigned to G, and its index will be assigned to I. For each grapheme, byte index denotes the index in the string where the bytes of its code point close to reside, but to determine the size in bytes of the cluster, we have to look at the byte index of the next grapheme. Once we have the byte index and the number of bytes, we can slice the string to get the bytes of the individual grapheme, and then we can write these bytes to the string builder. Notice though that we slice twice, first to get a slice that starts at byte index, then second to truncate the slice to have a length of num bytes. Also note that we have to treat the last grapheme as a special case because its cluster runs to the end of the string. Anyway, once the loop is done, we return the assembled string from the string builder. The next sample defines a count words procedure that returns the count of each unique word in a string. It takes a string as input and returns a word count struct, which contains a map of strings to integers and a string that will contain all the words stored in the map. As we'll see, the word counts needs to retain the full string so that we can properly deallocate. First in the procedure, we convert the string to lowercase so that all repeated occurrences of a word have the same case. Notice that we are assigning to a newly declared variable with the same name as the input parameter. Odin doesn't let us reassign the value of a parameter variable, but we can effectively shadow it with another local variable of the same name. We could, of course, just pick a different name, but this seemed to make sense. In the next line, we create a word count struct with the lowercase string assigned to the string field. We then define an array of strings containing the delimiter characters we'll use to split the string. Next, the for in loop iterates over every string returned by split multi iterate from the strings package. This procedure does not actually return an array or slice of any kind of collection. Instead, it returns a string and a boolean. When such a procedure is called in the in clause of a for loop, it's the returned boolean that determines if the loop runs another iteration, and the other returned values are assigned to the loop variables. So, this loop here keeps iterating as long as split multi iterate returns true. Also notice that this split procedure takes a pointer rather than just a string. This allows the procedure to update the string. In each call, split multi iterate scans through the string to find the first occurrence of any of the delimiter strings. If none is found, then returns false, and the loop ends. If a delimiter is found, then the substring after the delimiter becomes the new value of input, and the substring before the delimiter is returned. Effectively, each iteration returns the first word of the input, and that word plus the first delimiter is truncated from the input string. Be clear though that nothing here is actually modifying the actual character data. All of the strings created in this loop here represent sub ranges of the string that was returned by the call to two lower. Anyway, in our loop now, we trim away any leading or trailing punctuation marks, which also understand returns just a subset of the original string rather than a newly allocated one. If the length of the word is zero, we skip it, but otherwise, we increment the count in the map associated with this key. When the loop finishes, the counts have all been tallied, and we return. Lastly, we have an additional procedure which deallocates the members of the word count struct. It is the responsibility of the count word color to eventually deallocate the word counts members by calling delete word counts. You might be unclear though where the members of the word count struct are getting allocated exactly as it's not super obvious if you're expecting to see calls to make procedures. Well, looking at the code again, the key stir field is assigned the newly allocated string returned by two lower and the data field is implicitly allocated with Odin's default allocator the first time we add a word to the map. Each time we add an additional word to the map, the map may get reallocated if it doesn't have sufficient space to store the new word. Be clear though that the map only stores the string values, not the actual character data referenced by those string values. The string keys we're adding to the map are all substrings of the string allocated by the two lower call, so when key stir is deallocated, that effectively deallocates all of the memory referenced by the key strings. In this next example, the procedure abbreviate converts a phrase to its acronym or if you're a pedant, it's initialism. For example, the string as soon as possible becomes ASAP. Hyphens in the input string are treated as word separators, so liquid crystal display becomes LCD. In the procedure, we use this pattern string constant as a regular expression. The backtick delimiters make this a raw string literal, meaning it can directly contain new lines and doesn't interpret backslashes as escape sequences. In this case a regular string literal would work just as well, but raw string literals are often useful for regex patterns. The create iterator procedure from the regex package creates an iterator over matches for the given phrase and pattern. In addition to the iterator, it returns an error, but we safely discard the error here because we can assume our pattern is valid. We also create a string builder so we can append letters of the abbreviation incrementally. For both the iterator and the string builder, we defer calls to their destructors so that they both get deallocated when execution leaves the procedure. In the for in loop, the in clause calls the match iterator procedure, which returns a capture, meaning a match, an index of the capture, which we discard, and a boolean that indicates whether another match was found. So, this loop iterates until match iterator returns false, and the reason the procedure requires a pointer to the iterator is so that it can update the iterator's internal cursor. Inside the loop then, we get the first letter of the first capture group, and then write this letter to the string buffer. Once the loop is finished, we get the string from the builder, get its conversion to uppercase, then return. Because the return string was newly allocated by the two upper call, the caller should eventually free the returned string. The next example defines a procedure that returns the words from a list of candidates that are anagrams of the target word. For example, for the target word solemn and candidate words lemons, cherry, melons, the procedure returns lemons and melons because they are anagrams of the target word solemn. In the procedure, we first get the lowercase conversion of the word, and then pass the lowercase string to a second procedure we define called letters in order. The letters in order procedure returns the runes of the string in sorted order. To store the anagrams we find, we create a dynamic array of strings before looping For each candidate, we also get its lowercase conversion and runes in sorted order. If the sorted runes of the candidate match the sorted runes of the target word, then they must be anagrams, and so we append the candidate to the result array. As a special case though, if the candidate exactly matches the target word, we don't count that as an anagram. After the loop, we return the full slice of the dynamic array. As usual, the caller should eventually free any allocated memory returned by a procedure, but in this case, we get back a slice rather than the original allocated dynamic array. That's not a problem though, because the slice references the same memory as that dynamic array, and so freeing the slice frees that memory allocated for the dynamic array. The only questionable detail is that unlike a dynamic array, a slice does not retain a reference to its allocator. So, a slice by itself does not indicate where the memory was allocated from. In this case though, the default allocator was used to allocate the dynamic array, so the caller can safely free the slice from the default allocator. In the next sample, we have a union called item, which is composed of two variant types, I32 and a slice of the union itself. Effectively, an item represents a recursive ordered hierarchy of other items, where each item is an I32 or more items. The flatten procedure takes a single item and flattens all I32s in its hierarchy into a slice. While such a problem can be solved by defining the flatten procedure to be recursive, instead here, the solution uses a manually created stack, as this is generally a more efficient way to traverse a hierarchy. First in the procedure, we allocate a dynamic array that will store the output I32s, and another dynamic array that will act as a stack for storing items as we traverse the hierarchy. We start off by pushing the input item to the stack before entering a loop that keeps iterating until the stack is empty. In the loop, we pop the last item from the stack using the built-in pop procedure, and then use a type switch to access the I32 or item slice that it holds. If the item holds an I32, we simply append it to the output array, but if the item holds an item slice, then we append all of its elements to the stack in reverse order. We go in reverse because the stack is consumed last in, first out. Eventually, this loop exhausts all of the items in the hierarchy, at which point we return the full slice of the output array. Like usual, the caller of this procedure should eventually deallocate the returned slice. Our next-to-last sample implements a ring buffer of ints. We define the ring buffer type as a struct with four members, a slice of ints to store the elements, an integer representing the size, meaning the number of slots that are currently occupied, an integer representing the index of the current head, and a reference to the allocator which was used to allocate the slice. In fact, in general, a struct that contains allocated members should also reference their allocators so that they can be freed or reallocated later. Now, some operations we'll define for the ring buffer will potentially fail, so we define a ring error enum type with three values, none, meaning no error, buffer empty, meaning the buffer was empty when it wasn't expected to be, and buffer full, meaning the buffer was full when it wasn't expected to be. So, for the first operation, we define a procedure new buffer that returns a ring buffer with a newly allocated slice of elements. The interesting feature here is that the second parameter is given a default value, the context allocator, and also the type of this parameter is left inferred from the assignment. The subtle thing here is that a default value expression is evaluated in the scope of each call. So, when we call this procedure with only one argument, the allocator defaults to whatever value context.allocator has in that calling scope. Effectively, then, this procedure defaults to whatever context.allocator is active at the call site. The second procedure, destroy buffer, deallocates the buffer slice using the referenced allocator. As extra precautions, this procedure also sets the size and head to zero to help prevent misuse of the buffer struct after it's been destroyed. In fact, the other buffer procedures are all defined to do nothing or return errors when passed a zero value ring buffer struct. The third procedure, clear, simply sets the head and size to zero, which logically removes all values. The fourth procedure, read, returns the element at the head index and advances the head to the next logical index. For safety, we first check if the buffer is empty, in which case we return the buffer empty error. Then we get the value at the head index of the slice, and then increment the head index by one, wrapping back to zero if the head was already at the end of the slice. Because this operation removes an element, we decrement the size by one before returning the read value and error value none. The fifth procedure, write, appends an element at the logical end of the buffer, but first checks if the buffer is already full, in which case it returns the buffer full error. Otherwise, we compute the index by adding the current size to the current head, again wrapping back around if this exceeds the end of the slice. We then write the value to this index, increment the size by one, and return error value none. The sixth procedure, overwrite, also appends an element at the logical end of the buffer, but if the buffer is already full, overwrite clobbers the current head and advances the head to the next index. So, in the body, we call write, and if it returns the buffer full error, we overwrite the head value and increment the head index, wrapping if necessary. Our last example implements another collection structure, a linked list. Unlike our ring buffer, our linked list is a para poly struct, aka a generic struct, allowing us to create linked lists of any element type. As denoted by the dollar sign prefix, the type ID parameter T of the list struct requires a compile time argument. T effectively then functions as a type parameter, and in the struct we have three members, a head and a tail node plus a reference to the allocator of the nodes. The node type itself also has a dollar sign T type ID parameter and has three members, two node pointers, previous and next, plus the actual value stored in the node. So, for example, if we create a list where T is a string, then the nodes of this list will contain strings. Because some operations on lists potentially may fail, we also define an enum error type with two values, none, meaning no error, and empty list, meaning the list was empty when it wasn't expected to be. The first procedure, new list, returns a newly allocated list. The first parameter expects a compile time type ID, which determines the type of list created. The use of double dots on the last parameter type makes this procedure variadic, meaning it can be called with any number of T values. Concretely, this elements parameter is a slice of T, and all the T arguments to a call are collected into a slice that is passed to elements. In the body, we first create a list of T struct, making sure to set the allocator. We then loop over every element along with its index and create a node for each. The procedure new allocates memory for a single value of the provided type, in this case node of T, and returns a pointer to that allocation. We then set the value for the node and set its previous pointer to the current tail of the list, which is initially null. If this is the first node of the list, we make the node the head, but otherwise we update the tail to reference it as the the node. Lastly, we make the new node the tail of the list. Once a new node has been created for each element, we return the list. The second procedure, destroy list, deallocates all of the nodes of the list. Notice the syntax for the list parameter. This is saying that the parameter is a pointer to a list of T, where T can be any type. To deallocate the nodes, we simply loop through them, starting with the head and follow every next pointer until it reach a null pointer. For the actual deallocation, we call the built-in procedure free, which is the counterpart of the new procedure. The remaining procedures I'll just summarize quickly. The third procedure, unshift, inserts a value at the head of the list. The fourth procedure, push, adds a value to the tail of the list. The fifth procedure, shift, removes and returns the value at the head of the list. The sixth procedure, pop, removes and returns the value at the tail of the list. The seventh procedure, reverse, reverses the elements of the list without making any new allocations. The eighth procedure, count, returns the number of elements in the list. And the last procedure, remove first, removes the first element from the list which matches the provided value. If there is no matching value, the list is unchanged. The implementations of these procedures don't use any Odin features we haven't seen already, but I will note one interesting detail in the shift and pop procedures. These procedures free a node, but they also read the value of that same node when they return. So, to avoid a read-after-free error, these procedures defer the free calls so that they're only freed after the return executes. Now, in most cases, the read-after-free wouldn't be an actual problem here because we know for a fact that no new memory is allocated between the free and the return. However, with some allocators, a free call might immediately update the program's page tables, in which case a read-after-free trigger a page fault. Hence, deferring these free calls is the proper thing to do. Or alternatively, of course, we could simply just copy the return value to a local variable before safely freeing without deferring.