WEBVTT 00:00:00.058 --> 00:00:01.078 You write a pattern, 00:00:01.161 --> 00:00:05.086 you hand it to a library, and a moment later you have your matches back. 00:00:05.283 --> 00:00:08.926 I have used regular expressions almost every working day for years, 00:00:09.009 --> 00:00:12.853 and for most of that time I had no picture at all of what happens in between. 00:00:14.249 --> 00:00:17.861 It turns out to be something small and completely concrete. 00:00:18.174 --> 00:00:20.926 So that is the question for the next twenty minutes. 00:00:21.123 --> 00:00:24.676 What actually runs when a regular expression matches a string? 00:00:25.287 --> 00:00:27.700 We are going to build one of these machines by hand, 00:00:27.783 --> 00:00:29.117 feed a string through it, 00:00:29.200 --> 00:00:34.169 watch it turn into a faster machine, and then find two things it flatly cannot do. 00:00:34.711 --> 00:00:36.868 Start as small as anything can be. 00:00:36.951 --> 00:00:39.260 Here is the pattern a b. 00:00:39.343 --> 00:00:42.467 One a, then one b, and nothing else. 00:00:42.663 --> 00:00:44.383 And here is its machine. 00:00:44.692 --> 00:00:47.593 Three circles. They are called states, 00:00:47.676 --> 00:00:51.426 and the machine is sitting in exactly one of them at any moment. 00:00:51.623 --> 00:00:53.156 The little arrow on the left marks 00:00:53.156 --> 00:00:57.243 where it starts, so before it reads anything it is in q nought. 00:00:58.295 --> 00:01:00.976 The arrows between the circles are transitions, 00:01:01.059 --> 00:01:03.196 and each one carries a character. 00:01:03.392 --> 00:01:09.709 This one says: if you are in q nought and the next character is an a, move to q one. 00:01:09.813 --> 00:01:14.237 This one says: from q one, a b takes you to q two. 00:01:14.940 --> 00:01:19.084 And that second circle drawn around q two is the whole point of the picture. 00:01:19.167 --> 00:01:20.524 It means accepting. 00:01:20.607 --> 00:01:24.378 If the string runs out while the machine is sitting there, the pattern matched. 00:01:24.461 --> 00:01:27.399 If it runs out anywhere else, it did not. 00:01:28.103 --> 00:01:29.971 So feed it the string a b. 00:01:30.054 --> 00:01:32.026 We begin in q nought. 00:01:32.109 --> 00:01:36.742 The first character is an a, so we follow the a arrow and land on q one. 00:01:36.846 --> 00:01:40.225 The next character is a b, which carries us to q two. 00:01:40.929 --> 00:01:43.958 The string has run out and we are sitting in the accepting state, 00:01:44.041 --> 00:01:45.574 so this one matched. 00:01:45.678 --> 00:01:49.997 Two characters, two arrows, no searching and no going back. 00:01:50.538 --> 00:01:52.757 Now feed it a a instead. 00:01:52.953 --> 00:01:56.286 The first a is fine and puts us in q one. 00:01:56.390 --> 00:02:01.069 Then the second a arrives, and there is no arrow out of q one labelled a. 00:02:01.266 --> 00:02:05.737 The machine has nowhere to go, so it stops, and it reports no match. 00:02:06.533 --> 00:02:08.447 That is the whole vocabulary. 00:02:08.530 --> 00:02:14.591 States, transitions, one place to start, and one or more accepting states. 00:02:14.788 --> 00:02:19.061 Everything for the rest of this lecture is that same picture with more arrows on it. 00:02:20.155 --> 00:02:22.338 Here is the thing nobody tells you. 00:02:22.442 --> 00:02:24.124 The machine is not guessed at, 00:02:24.207 --> 00:02:28.074 it is computed, and it follows the shape of the expression. 00:02:28.270 --> 00:02:32.576 There are only four kinds of piece in a basic regular expression, 00:02:32.659 --> 00:02:35.307 and each one has its own translation. 00:02:36.104 --> 00:02:39.680 A single character is one arrow between two states. 00:02:39.877 --> 00:02:42.966 That is rule one and that is the whole of it. 00:02:43.670 --> 00:02:45.746 A choice, written a bar b, 00:02:45.829 --> 00:02:50.428 is two arrows leaving the same state, one for each alternative. 00:02:50.624 --> 00:02:55.315 Whichever character actually turns up, one of those arrows is available to take. 00:02:56.112 --> 00:02:59.930 A star means any number of repetitions, including none at all, 00:03:00.013 --> 00:03:03.496 and that is an arrow that comes straight back to the state it left. 00:03:03.809 --> 00:03:07.096 Go round it as often as you like, or never. 00:03:07.799 --> 00:03:11.106 And concatenation, writing one piece after another, 00:03:11.189 --> 00:03:14.325 glues the end of the first onto the start of the second. 00:03:14.429 --> 00:03:18.666 Four rules, and between them they translate anything built from characters, 00:03:18.666 --> 00:03:21.279 choice, star and concatenation. 00:03:22.076 --> 00:03:24.489 One honest note before we use them. 00:03:24.572 --> 00:03:27.741 The textbook construction bolts a couple of extra bookkeeping 00:03:27.741 --> 00:03:32.653 states onto every single piece, so the drawing gets enormous very fast. 00:03:32.850 --> 00:03:35.707 I am going to draw the tidied result instead. 00:03:35.903 --> 00:03:39.979 It accepts exactly the same strings, and you can actually see it. 00:03:41.376 --> 00:03:44.128 Now a pattern you might genuinely write. 00:03:44.580 --> 00:03:49.759 Bracket, a bar b, close bracket, star, then a b b. 00:03:50.072 --> 00:03:51.976 In words: any number 00:03:51.976 --> 00:03:57.248 of a's and b's, and then the string has to finish with the letters a, b, b. 00:03:57.789 --> 00:03:59.427 Take the star first. 00:04:00.041 --> 00:04:04.091 Rule two says the choice inside it is two arrows off one state, 00:04:04.174 --> 00:04:07.888 and rule three says the star sends them back where they came from. 00:04:07.971 --> 00:04:13.067 So both arrows leave q nought and both return to q nought, and I have drawn them 00:04:13.067 --> 00:04:15.483 as one loop carrying two labels. 00:04:16.279 --> 00:04:20.599 Read that loop as: sit here and swallow whatever you like. 00:04:20.703 --> 00:04:26.067 Now rule four, concatenation, glues the rest of the pattern onto the end of it. 00:04:26.608 --> 00:04:31.553 The rest is three plain characters, so rule one gives us three arrows in a row. 00:04:31.636 --> 00:04:34.783 An a takes us from q nought to q one. 00:04:35.095 --> 00:04:37.627 A b takes us on to q two. 00:04:37.824 --> 00:04:40.576 And a final b takes us to q three. 00:04:41.489 --> 00:04:44.436 And q three is the accepting state, 00:04:44.519 --> 00:04:48.804 because arriving there is exactly what it means to have finished with a b b. 00:04:49.001 --> 00:04:53.495 Four states, five arrows, and every one of them came off a rule. 00:04:54.291 --> 00:04:58.321 Now look hard at q nought, because there is something wrong with it. 00:04:58.517 --> 00:05:01.976 Two different arrows leave that state carrying the letter a. 00:05:02.059 --> 00:05:05.194 One is the loop and one goes to q one. 00:05:05.991 --> 00:05:09.927 So when an a arrives, the machine has no way to decide. 00:05:10.124 --> 00:05:12.212 Is this a in the middle of the string, 00:05:12.295 --> 00:05:15.790 or is it the a that starts the ending we are looking for? 00:05:15.987 --> 00:05:19.239 It cannot know until it has read what comes after. 00:05:19.435 --> 00:05:22.037 That is what nondeterministic means. 00:05:23.851 --> 00:05:26.069 The fix is not to decide. 00:05:26.173 --> 00:05:28.993 Here is an input string, a a b b, 00:05:29.076 --> 00:05:32.757 and here is the list of states the machine could possibly be in. 00:05:33.069 --> 00:05:37.552 Before we read anything that list has exactly one entry, q nought. 00:05:38.349 --> 00:05:43.618 Read the first a. From q nought, two arrows are labelled a: the loop, 00:05:43.701 --> 00:05:47.336 which keeps us where we are, and the one across to q one. 00:05:47.648 --> 00:05:50.877 We refuse to choose, so we take both. 00:05:50.980 --> 00:05:55.462 The machine is now in q nought and q one at the same time. 00:05:56.259 --> 00:06:02.413 Read the second a. From q nought we get q nought and q one all over again. 00:06:02.725 --> 00:06:08.322 From q one there is no a arrow at all, so that possibility simply dies. 00:06:08.519 --> 00:06:14.081 The set has not changed, but the q one in it is a brand new thread, not the old one. 00:06:14.878 --> 00:06:15.735 Read a b. 00:06:15.818 --> 00:06:21.482 The loop keeps q nought alive, and from q one the b arrow moves us on to q two. 00:06:21.565 --> 00:06:25.487 So the live set is now q nought and q two, 00:06:25.570 --> 00:06:29.089 and the thread that was in q one has moved along with it. 00:06:30.001 --> 00:06:33.636 Suppose the string stopped right here, at a a b. 00:06:33.833 --> 00:06:36.606 We would be holding q nought and q two, 00:06:36.689 --> 00:06:39.522 and neither of those is an accepting state. 00:06:39.719 --> 00:06:45.142 So that string does not match, and we can say so without trying anything else. 00:06:46.054 --> 00:06:47.831 But it does not stop. 00:06:48.028 --> 00:06:49.443 Read the last b. 00:06:49.526 --> 00:06:51.718 The loop keeps q nought once more, 00:06:51.801 --> 00:06:56.295 and from q two the b arrow carries us into q three. 00:06:57.347 --> 00:07:01.107 Now the string has run out and one of the states we are holding is accepting, 00:07:01.190 --> 00:07:02.816 so the pattern matched. 00:07:03.268 --> 00:07:05.565 And that is the rule in general. 00:07:05.648 --> 00:07:10.514 If any possibility in your live set is an accepting state, it is a match. 00:07:11.566 --> 00:07:13.854 Notice what we never had to do. 00:07:14.050 --> 00:07:17.464 We never backed up and tried a different route through the pattern. 00:07:17.777 --> 00:07:19.344 We carried every possibility 00:07:19.344 --> 00:07:23.095 forward together and we read each character exactly once. 00:07:23.408 --> 00:07:25.751 Nondeterministic does not mean guessing. 00:07:25.834 --> 00:07:29.051 It means holding several answers at the same time. 00:07:30.170 --> 00:07:35.277 That machine works, and it is honest about not knowing. But look at what it costs. 00:07:35.360 --> 00:07:38.423 On every character we had to take a whole set of states, 00:07:38.506 --> 00:07:42.524 follow every arrow out of every one of them, and build the next set. 00:07:43.228 --> 00:07:48.081 So here is the idea that fixes it, and it is almost embarrassingly simple. 00:07:48.394 --> 00:07:50.877 Those sets are the only thing that ever mattered. 00:07:50.960 --> 00:07:53.654 So make each set a state in its own right. 00:07:54.451 --> 00:07:57.676 Then the new machine has no choices left in it anywhere. 00:07:57.759 --> 00:08:01.057 One state, one character, one next state. 00:08:01.161 --> 00:08:03.214 That is what deterministic means, 00:08:03.297 --> 00:08:07.257 and it is why the second machine can be a table you index into. 00:08:08.560 --> 00:08:13.112 First write down the old machine as a table, straight off the diagram. 00:08:13.309 --> 00:08:19.753 From q nought an a goes to q nought and q one, and a b goes back to q nought. 00:08:20.689 --> 00:08:25.078 From q one, an a goes nowhere and a b goes to q two. 00:08:25.565 --> 00:08:28.631 From q two, a b goes to q three. 00:08:28.734 --> 00:08:31.568 And q three has no arrows out of it at all. 00:08:32.283 --> 00:08:36.591 Now start the new machine from the only set we know, the one we begin in. 00:08:37.078 --> 00:08:38.611 Just q nought. 00:08:38.808 --> 00:08:40.167 Call it A. 00:08:40.871 --> 00:08:44.410 From A on an a, the table says q nought and q one. 00:08:44.493 --> 00:08:48.418 That is a set we have not met before, so it earns a name of its own. 00:08:48.614 --> 00:08:54.223 Call it B. From A on a b, we get just q nought again, which is A itself. 00:08:54.706 --> 00:08:57.783 Now do B, which is q nought and q one. 00:08:57.910 --> 00:09:02.982 On an a, q nought gives q nought and q one, and q one gives nothing. 00:09:03.065 --> 00:09:04.468 So we land back on B. 00:09:04.551 --> 00:09:11.039 On a b, q nought gives q nought and q one gives q two, so we get q nought and q two. 00:09:11.122 --> 00:09:13.294 New set. Call it C. 00:09:13.557 --> 00:09:16.750 Then C, which is q nought and q two. 00:09:16.923 --> 00:09:20.744 On an a we get q nought and q one, which is B again. 00:09:20.906 --> 00:09:25.353 On a b, q two gives q three, so we get q nought and q three. 00:09:25.526 --> 00:09:27.083 One more new set. 00:09:27.256 --> 00:09:28.476 Call it D. 00:09:28.739 --> 00:09:31.851 And finally D, which is q nought and q three. 00:09:32.024 --> 00:09:33.323 On an a we get B. 00:09:33.406 --> 00:09:38.631 On a b, q three gives nothing, so we get plain q nought, which is A. 00:09:39.323 --> 00:09:42.087 And that is the moment the whole thing stops. 00:09:42.377 --> 00:09:45.199 Every set we reached was already on the list. 00:09:45.790 --> 00:09:49.378 Four sets, and the search has nothing left to find. 00:09:50.867 --> 00:09:52.226 So draw them. 00:09:52.400 --> 00:09:55.312 Four states, A, B, C and D, 00:09:55.395 --> 00:10:00.609 and now every state has exactly one arrow leaving it for a and exactly one for b. 00:10:01.382 --> 00:10:05.586 From A an a goes to B, and a b comes straight back to A. 00:10:05.875 --> 00:10:09.812 From B an a stays on B, and a b drops down to C. 00:10:10.574 --> 00:10:14.717 From C an a climbs back to B, and a b carries on to D. 00:10:14.800 --> 00:10:19.584 And from D an a cuts across to B, while a b returns to A. 00:10:20.125 --> 00:10:21.435 Which one accepts? 00:10:21.518 --> 00:10:24.526 D does, and for one reason only. 00:10:24.723 --> 00:10:27.252 D is the set that contains q three, 00:10:27.335 --> 00:10:31.109 and q three was the accepting state of the old machine. 00:10:31.213 --> 00:10:36.032 That is the whole rule: a set accepts when anything in it accepts. 00:10:36.735 --> 00:10:42.922 And now run a a b b through this one. We start in A. The first a takes us to B. 00:10:43.005 --> 00:10:45.211 The second a keeps us there. 00:10:45.315 --> 00:10:49.983 Then a b drops us down to C, and the final b carries us into D. 00:10:50.594 --> 00:10:52.636 One state at every moment. 00:10:52.719 --> 00:10:57.166 No sets, no threads, and a single table lookup for each character. 00:10:57.270 --> 00:10:59.892 That is about as fast as a matcher can be, 00:10:59.975 --> 00:11:03.017 and it does not care how complicated the pattern was. 00:11:03.121 --> 00:11:05.838 There is a catch, though, and it is a big one. 00:11:06.957 --> 00:11:09.756 Here is a pattern that looks completely harmless. 00:11:09.952 --> 00:11:15.015 Any number of a's and b's, then an a, then any two characters. 00:11:15.467 --> 00:11:19.392 Read in plain English, it says the third character from the end is an a. 00:11:20.189 --> 00:11:23.847 Translate it with the same four rules and you get four states. 00:11:24.043 --> 00:11:27.722 A loop that swallows anything, an a that commits, 00:11:27.805 --> 00:11:30.940 and then two arrows that will take whatever they are given. 00:11:31.737 --> 00:11:36.277 That is a small machine, and simulating it with a live set is cheap. 00:11:36.381 --> 00:11:39.354 At most four states are ever alive at once. 00:11:39.969 --> 00:11:42.616 Now determinise it and watch what happens. 00:11:43.831 --> 00:11:47.544 The deterministic machine is not allowed to hold possibilities. 00:11:47.627 --> 00:11:50.391 When an a arrives it has to commit right then to whether 00:11:50.391 --> 00:11:52.725 this is the a we are looking for. 00:11:52.829 --> 00:11:54.325 But it cannot know that, 00:11:54.408 --> 00:11:57.822 because the answer depends on how many characters come afterwards. 00:11:58.619 --> 00:12:00.660 So it does the only thing left. 00:12:00.743 --> 00:12:03.319 It remembers the last three characters it has seen, 00:12:03.402 --> 00:12:07.315 and when the input finally ends it looks at the oldest of the three. 00:12:08.019 --> 00:12:10.121 How many things is that to remember? 00:12:10.225 --> 00:12:15.032 Two possibilities for each of three positions. Two times two times two. 00:12:15.136 --> 00:12:19.014 Eight states, where the nondeterministic machine had four. 00:12:19.927 --> 00:12:22.192 Now replace the three with an n. 00:12:22.388 --> 00:12:27.054 The nondeterministic machine grows very gently: it needs n plus one states, 00:12:27.137 --> 00:12:30.330 one for each position it still has to watch go by. 00:12:30.527 --> 00:12:32.292 That is the green line. 00:12:33.089 --> 00:12:37.234 The deterministic one has to remember the last n characters, and the number 00:12:37.234 --> 00:12:41.321 of things it might need to remember is two to the n. That is the red one. 00:12:42.025 --> 00:12:47.459 At n equals three the two are still close. Push it to five and the gap has opened. 00:12:47.563 --> 00:12:51.543 Push it to eight and the red curve has left the picture behind entirely, 00:12:51.626 --> 00:12:54.019 while the green one has crawled up to nine. 00:12:54.444 --> 00:12:55.800 Put some numbers on it. 00:12:55.883 --> 00:13:00.398 With n of ten, eleven states have become one thousand and twenty four. 00:13:00.481 --> 00:13:02.605 Push n up to twenty and those twenty 00:13:02.605 --> 00:13:06.716 one states have become the figure on the bottom row, which is over a million. 00:13:07.257 --> 00:13:09.685 And nobody has done anything wrong here. 00:13:09.788 --> 00:13:12.343 This is not a bug in an implementation. 00:13:12.447 --> 00:13:14.967 It is the price of removing the choices. 00:13:15.071 --> 00:13:17.973 The choices were carrying information, and if you refuse 00:13:17.973 --> 00:13:21.875 to defer them, you have to store that information as states instead. 00:13:22.672 --> 00:13:25.667 Which is why serious engines mostly do not build the whole 00:13:25.667 --> 00:13:27.792 deterministic machine up front. 00:13:27.989 --> 00:13:32.830 Some simulate the nondeterministic one directly, carrying the live set exactly 00:13:32.830 --> 00:13:35.489 as we did by hand a few minutes ago. 00:13:36.286 --> 00:13:39.001 Others build deterministic states lazily. 00:13:39.084 --> 00:13:42.902 They construct a state the first time some input actually reaches it, 00:13:42.985 --> 00:13:46.666 cache it, and throw the cache away when it grows too large. 00:13:46.770 --> 00:13:50.962 You pay for the states your data really visits and not for the ones it never does. 00:13:52.004 --> 00:13:55.009 One last limit, and this one is not about size. 00:13:55.092 --> 00:13:58.399 It is about something a regular expression cannot do at all, 00:13:58.482 --> 00:14:00.875 no matter how long you are willing to make it. 00:14:01.671 --> 00:14:03.355 Here is the language. 00:14:03.552 --> 00:14:05.280 Some number of opening brackets, 00:14:05.363 --> 00:14:09.274 followed by exactly the same number of closing brackets, and nothing else. 00:14:09.357 --> 00:14:11.294 Two open and two closed is in. 00:14:11.377 --> 00:14:12.769 Three and three is in. 00:14:12.852 --> 00:14:15.128 Two open and one closed is not. 00:14:15.925 --> 00:14:18.956 Everybody's first instinct is to reach for a star. 00:14:19.152 --> 00:14:22.728 There is no pattern that does it, and I want to show you why on the actual 00:14:22.728 --> 00:14:26.746 machine, because the argument is short and it is completely concrete. 00:14:28.259 --> 00:14:30.280 Suppose there were such a pattern. 00:14:30.476 --> 00:14:35.110 Then there is a machine for it, and that machine has some fixed number of states. 00:14:35.306 --> 00:14:38.372 It does not matter what the number is, so let us say four. 00:14:39.285 --> 00:14:42.525 Now feed it four opening brackets and nothing else yet. 00:14:42.721 --> 00:14:43.904 It starts somewhere, 00:14:43.987 --> 00:14:47.912 and each bracket moves it along, so we can watch the states it visits. 00:14:48.824 --> 00:14:50.334 Count the visits. 00:14:50.647 --> 00:14:53.433 Where it was before any bracket, then after one, 00:14:53.433 --> 00:14:56.046 after two, after three, after four. 00:14:56.661 --> 00:15:00.690 That is five visits, and I have written the count above each one. 00:15:01.487 --> 00:15:05.284 Five visits, and the machine only has four states to be in. 00:15:05.481 --> 00:15:08.439 So two of these five have to be the very same state. 00:15:08.522 --> 00:15:10.343 There is nowhere else for them to be. 00:15:10.426 --> 00:15:13.956 That is the whole of the argument, and it is just counting. 00:15:14.753 --> 00:15:16.388 Say it is this one and this one. 00:15:16.471 --> 00:15:17.898 Then they are not two states, 00:15:17.981 --> 00:15:20.942 they are one state that the machine passed through twice. 00:15:21.139 --> 00:15:22.637 Give it a name, q. 00:15:23.248 --> 00:15:25.606 And now look at what sits between them. 00:15:26.220 --> 00:15:30.735 The machine left q, read two opening brackets, and arrived back at q. 00:15:30.818 --> 00:15:34.464 That is a loop, and the machine has no way of knowing it went round it. 00:15:34.808 --> 00:15:36.583 So send it round twice. 00:15:36.666 --> 00:15:39.961 It reads two more opening brackets, comes back to q again, 00:15:40.044 --> 00:15:43.331 and it is in precisely the state it would have been in anyway. 00:15:43.434 --> 00:15:48.137 Then the four closing brackets do exactly what they did before, and it accepts. 00:15:48.934 --> 00:15:51.396 But count the string it has just accepted. 00:15:51.592 --> 00:15:55.378 Six opening brackets, and still only four closing ones. 00:15:55.992 --> 00:15:57.548 The machine has accepted something 00:15:57.548 --> 00:16:01.345 that is not balanced, which is the one thing we assumed it never did. 00:16:02.258 --> 00:16:04.245 And the four was arbitrary. 00:16:04.348 --> 00:16:08.306 Whatever number of states you name, I feed it that many opening brackets, 00:16:08.389 --> 00:16:12.337 count one more visit than it has states, and find the same loop. 00:16:12.441 --> 00:16:14.427 Every fixed number loses. 00:16:15.823 --> 00:16:17.693 So what actually went wrong? 00:16:18.006 --> 00:16:20.399 Not the star, and not the choice. 00:16:20.502 --> 00:16:22.500 The machine ran out of memory. 00:16:22.697 --> 00:16:25.563 To match brackets you have to remember how many are still open, 00:16:25.646 --> 00:16:27.724 and that number has no ceiling. 00:16:28.521 --> 00:16:32.571 A machine with a fixed number of states can remember a fixed number of things. 00:16:32.654 --> 00:16:33.999 That is the real boundary, 00:16:34.082 --> 00:16:38.483 and every language that needs to count without limit sits on the far side of it. 00:16:39.187 --> 00:16:41.730 Which is why the recursion and the backreferences 00:16:41.730 --> 00:16:46.119 in your favourite engine are not regular expressions in this sense at all. 00:16:46.223 --> 00:16:48.951 They are the features that step outside, and the price 00:16:48.951 --> 00:16:53.015 of stepping outside is that they can no longer be run as a finite machine. 00:16:53.812 --> 00:16:55.598 So that is the whole picture. 00:16:55.681 --> 00:17:00.651 Your pattern becomes a machine, one arrow per character, one state at a time. 00:17:00.755 --> 00:17:01.904 Nondeterminism means 00:17:01.904 --> 00:17:05.063 holding several possibilities together rather than guessing. 00:17:05.515 --> 00:17:10.659 Determinising trades those possibilities for states, sometimes at a terrible price. 00:17:11.362 --> 00:17:12.918 And a machine with a fixed number 00:17:12.918 --> 00:17:15.880 of states can only ever remember a fixed amount. 00:17:16.076 --> 00:17:20.546 Next time a pattern is slow, or refuses to do what you want at all, you now know 00:17:20.546 --> 00:17:23.008 which of those four facts you are standing on.