Handling long paths on Windows

Recently I was having a tough time trying to add support for long paths to some piece of software running on Windows OS. If you did some work with file I/O on Windows you would definitely know that file paths have a length limit, namely, MAX_PATH, which is 260. If we exclude the drive letter, colon, the backslash after colon and the terminating null character at the very end of the path, then 256 characters remain for the path on the drive: "<drive letter>:\\<max 256 characters long path>\0".

  However, if again you worked with I/O APIs, you would notice that some of them come in two different versions - ANSI and UNICODE, ending with 'A' and 'W', respectively. A good example is GetCurrentDirectory, with GetCurrentDirectoryW and GetCurrentDirectoryA specialized versions. Turns out that newer file systems on Windows always store the paths in Unicode so they can store any extended character and there's no need to truncate the path. That said, a Unicode path can be up to 32,767 characters long. Note, that even with Unicode each of the path components cannot be longer than some limit, which is to the best of my knowledge 255 (can be found in lpMaximumComponentLength out parameter of GetVolumeInformation function)  So the idea behind the Unicode versions of APIs is to support longer paths. A good start would be to read this article on MSDN to familiarize yourselves with the notions and basic details of file and path names.

  The main technique to learn is prefixing the full path name with '\\?\', or with escaped string "\\\\?\\", or if you are a C++ fan, LR"(\\?\)". This will make the path treated as a Unicode path which does not have the MAX_PATH limit. However, this prefix can be used with full paths only, so be sure to call GetFullPathNameW and prefix the value obtained from it. Beware, the MSDN page I linked to has some wrong guideline, it says if you want to get the Unicode version without the MAX_PATH restriction, prefix the input path string with \\?\, however, as I already mentioned, this prefix is valid only for full paths, so providing a relative path prefixed with it won't ever work. Just make sure you call the Unicode version of the function. After this point, any path like ..\a\b\myFile.txt will be converted to something like C:\work\a\b\myFile.txt, even if the last path has more than MAX_PATH characters, and after prefixing it will look like \\?\C:\work\a\b\myFile.txt. Now you can use this path to open a stream and read the file contents (make sure you always use the Unicode versions of APIs, there are some that do not have it, e.g. OpenFile). You can correctly guess, that GetFullPathName does not need the path to represent an existing file, it can be something made up, and the relative root will be considered the current working directory, that's how the parent nodes will be identified.

  If you need to deal with not only local paths, but also remote shares, there is a slight difference you need to remember. The prefix for remote paths is not '\\?\', but rather '\\?\UNC\'. The full path returned by GetFullPathName function (or its Unicode or ANSI versions) will have the form <Drive letter>:\<directory path>\<filename> for local paths. For network shares it will have this form: \\<Server name>\<share path>\<filename>. So to determine which prefix you need to add, you just need to check the first two characters of the full path (assuming valid paths, but not necessarily existing). One last small but important thing; when you get a server share path, you cannot just prefix it with '\\?\UNC\', you need to remove the leading '\\' first, so that you do not end up with \\?\UNC\\\<Server name>... (note the three consecutive backslashes after UNC).

  The second big piece to know about is short paths. The most common way of creating short paths on Windows is the 8.3 pattern coming from DOS. It's called 8.3 because there are 8 characters for file name a point and then 3 characters for extension. Any path that is longer than MAX_PATH, can be represented as a short version of it by modifying one or more (until the total length is not greater than MAX_PATH) of its components to match the 8.3 pattern (note, that this is not the only possible way, so do not rely on the pattern itself, but use the APIs). I.e. for instance if we have a file file.txt under directory aaa...aa consisting of 100 'a'-s (<100a> from now on), which itself is under <100b> and the latter is under <100c> on drive D:, then the full path will contain wcslen(L"file.txt") + 3*100 + wcslen(L"D:\") + 1 (this last one for the terminating null character), which is 309, which obviously is greater than MAX_PATH. So shortening this will be take the first path component that does not match the 8.3 patten, which is <100a>, and shorten it to aaaaaa~1, as you can see it's 8 characters now, and with just one component modification the total length is reduced to 309-92=217, which is good to go.

  If somewhere in your program you have a file path which is coming as an input, always consider that it can be in a short form, and calling GetFullPathNameW on it, won't actually expand the short components to full ones, it will just get the full path from the root to the file, but containing the same short component names, i.e. aaaaaa~1 will become D:\aaaaaa~1. In order to get the expanded version of full path, call GetLongPathNameW function, but remember to prefix the full path with \\?\. In contrast to GetFullPathName, GetLongPathName requires that the path represent an actual file/directory on disc.

  That's it, after this point all the APIs that are internally supporting long paths, will work fine with the full expanded version of file name. I managed to open a stream on a file whose path length was 457. It took me a lot of time to create that file. Windows Explorer does not support long paths, but seems there are some bugs, so you can get to it. If you try to create a file whose full path name will be longer than MAX_PATH, it will not allow you. But if you create it shorter, then start renaming the containing directories, you can make it. If you try to copy the full path from the address bar in windows explorer, or do a Shift+right click on the file, and 'Copy As Path' from context menu, then it will store the short version of the full path in the clipboard.

  Since I used a lot of different APIs and in most of them I converted the path, I also added a check to my conversion function to consider the input path full if it already starts with the long path prefix (\\?\).

  As I already mentioned, some functions do not support long paths. One important instance is CreateProcessW, Although you can specify a command line parameter up to 32767 characters long, the executable path part is limited to MAX_PATH. The best option I found out is to get the short version of the full path, which will implicitly support ~MAX_PATH/9*255 path length, since each component in short version might contain 8 characters only, so we could have MAX_PATH/9 (8 characters for path component and 1 separator - slash or backslash) components, but in the long version each of them can be up to 255 characters long. This estimate is far from being precise, since it does not consider the drive name, the file name, and also implies too long component names which rarely happens. So in some specific cases shortening the full path helps, but that is not a portable solution, since not all file systems support short names and even the ones that do do not always have the same pattern for shortening.

  Seems this is all I wanted to share, I spent a lot of time researching the web to get a working model, and I did a lot of tests myself, before I updated the original code, so thought some people might find my experience useful.

P.S. A side note on file/path APIs

Whenever there is an API that accepts a buffer to fill and the number of characters to fill, it generally accepts a null and 0, respectively, for those arguments, and just returns the required number of characters to store the to-be-returned string. So you can just call with null and 0 first, and then allocate a buffer of correct size, not to do it twice. Let's look at one of the functions discussed above.

// consider an input fileName of type PCWSTR (const wchar_t*)

DWORD requiredBufferLength = GetFullPathNameW(fileName, 0, nullptr, nullptr);

if (0 == requiredBufferLength) // means failure

{

       return GetLastError();

}

wchar_t* buffer = new wchar_t[requiredBufferLength];

DWORD result = GetFullPathNameW(fileName, requiredBufferLength, buffer, nullptr);

if (0 == result)

{

       return GetLastError();

}

// buffer now contains the full path name of fileName, use it.

Find occurrences of an integer in a sorted array

    Recently I was given a problem to solve during a technical interview: we have an array of sorted integers as an input and a single integer; we need to find the starting and ending positions of the occurrences of that integer in the array. For example, if the array is {0, 1, 1, 2, 3, 4, 4, 4, 5} and the input integer is 1, the program should return (1, 2). If the input integer is 4 and the array is the same, the program should return (5, 7). And finally, if no occurrence found, say if the input is 7, the program should return (-1, -1). I couldn't get a clean code in the assigned time, that's why I decided to try it at home and make sure my algorithm works. So here is just a simple solution. For simplicity, I used std::vector<int> as an input array, but obviously it should be a generalized function with a template parameter. Anyway, here is my solution:

// The actual interface method which is the solution to the problem

std::pair<int, int> getRange(const std::vector<int>& numbers, int value)

{

       return getRange(numbers, 0, numbers.size(), value, -1, -1);

}

As you can see, in the function above I am just calling an overloaded version of the same function, which contains the actual algorithm implementation. I added lots of explanatory comments so no more text, just the code:

// Obviously this should be just an implementation detail

// so you don't want this be part of an interface of your

// class/lib.

// Note the currentLow and currentUp parameters, they are

// meant to keep track of the so-far-found range of

// occurrences, to pass down to the same function through

// recursive calls.

std::pair<int, int> getRange(

       const std::vector<int>& numbers,

       int begin,

       int end,

       int value,

       int currentLow = -1,

       int currentUp = -1)

{

       // First of all, since the original array is sorted,

       // we don't need to look for anything if the element

       // we're looking for is less than the first

       // element of the array or greater than the last,

       // meaning that it's not there for sure. So just

       // returning the not found value.

       if (value < numbers[begin] || value > numbers[end - 1])

       {

              return std::make_pair(currentLow, currentUp);

       }

       // On the other hand, if the first and last elements

       // of the array are equal to the one we're looking for,

       // it means all the elements between are also equal

       // because the array is sorted. Hence, we just return

       // the whole range.

       if (numbers[begin] == value && numbers[end - 1] == value)

       {

              return std::make_pair(begin, end - 1);

       }

       // If none of the easy cases happen, then we just

       // split the array in two, and try to look for the

       // range in a binary search fashion.

       int middle = begin + (end - begin) / 2;

       // If the middle element is greater than the value, then

       // obviously, if the element is in the array, it's in the

       // first half (left from middle), so we just call the

       // function recursively with the cut range.

       if (value < numbers[middle])

       {

              // look in first half

              return getRange(

                     numbers,

                     begin,

                     middle,

                     value,

                     currentLow,

                     currentUp);

       }

       // Same here - but looking in the other half.

       else if (value > numbers[middle])

       {

              // look in 2nd half

              return getRange(

                     numbers,

                     middle,

                     end,

                     value,

                     currentLow,

                     currentUp);

       }

       // This is the most interesting case, when middle element

       // is equal to the given value, it means there might be

       // occurrences both on left and right sides. Now we call

       // the function recursively for both left and right

       // sections, but we only take the lower bound from left

       // section and the upper bound from the right.

       else

       {

              currentLow = (currentLow > middle || currentLow == -1) ?

                                         middle : currentLow;

              currentUp = (currentUp < middle) ? middle : currentUp;

             

              // look in both

              int lowerBound = getRange(

                     numbers,

                     begin,

                     middle,

                     value,

                     currentLow,

                     currentUp).first;

              int upperBound = getRange(

                     numbers,

                     middle,

                     end,

                     value,

                     currentLow,

                     currentUp).second;

              return std::make_pair(lowerBound, upperBound);

       }

}

Don't forget to include the required headers.

How to convert string to DateTime and vice versa

Recently I was looking for a convenient way, to parse a string representation of DateTime to integral value representing epoch time. And I couldn't find an existing class to make that easily, for example giving the string as an input to constructor. After about a couple of hours of research I found a brief way to achieve that using a mix of C and C++ tools.

First of all, there is an std::tm struct defined in <ctime> header, which represents a calendar date and a time with all the relevant members, the date is reckoned from start of year 1900, thus, if we try to represent current year (2014) the year field of tm structure will be equal to 114.

Second, in the same <ctime> header there is an auxiliary function, mktime, which accepts a pointer to std::tm object and returns std::time_t. The latter is a typedef not defined by C++ standard specification. However, it is almost always an integral type, so we can store it in an std::int64_t to be on the safe side. std::time_t represents the number of seconds elapsed since epoch (Jan 1 1900, 00:00:00), the same as POSIX time.

Alright, now that we have found a good type to store date and time in, we need the last step, getting all this info from a string, and that is where the most difficult part comes. std::tm is a POD struct, so no parse methods for users. std::time_t is just a typedef of a built-in type, so again, not much use.

Fortunately, there is a great set of tools that help developers deal with streams, and one of them is i/o manipulators. The one that we are going to use here is std::get_time from <iomanip> header. If passed as an argument to input stream's operator>>, it formats the stream buffer with the provided format string and writes the resulting dateTime into an std::tm structure. And that solved my problem.

Enough text, let's look into the code:

#include <ctime>

#include <iomanip>

#include <iostream>

#include <sstream>

// Converts UTC time string to a time_t value.

std::time_t getEpochTime(const std::wstring& dateTime)

{

       // Let's consider we are getting all the input in

       // this format: '2014-07-25T20:17:22Z' (T denotes

       // start of Time part, Z denotes UTC zone).

       // A better approach would be to pass in the format as well.

       static const std::wstring dateTimeFormat{ L"%Y-%m-%dT%H:%M:%SZ" };

       // Create a stream which we will use to parse the string,

       // which we provide to constructor of stream to fill the buffer.

       std::wistringstream ss{ dateTime };

       // Create a tm object to store the parsed date and time.

       std::tm dt;

       // Now we read from buffer using get_time manipulator

       // and formatting the input appropriately.

       ss >> std::get_time(&dt, dateTimeFormat.c_str());

       // Convert the tm structure to time_t value and return.

       return std::mktime(&dt);

}

int main(void)

{

       // Test to see if our function works properly.

       std::wstring dateTimeStr{ L"2014-07-25T20:17:22Z" };

       std::wcout << L"The epoch time value representing " << dateTimeStr

              << L" is " << getEpochTime(dateTimeStr) << std::endl;

       return 0;

}

If you want to verify that get_time correctly populated the tm object, just add a couple of outputs  after operator>> line, something like this:

       std::wcout << dt.tm_year << std::endl;

       std::wcout << dt.tm_mon << std::endl;

       std::wcout << dt.tm_mday << std::endl;

       std::wcout << dt.tm_hour << std::endl;

       std::wcout << dt.tm_min << std::endl;

       std::wcout << dt.tm_sec << std::endl;

To convert the epoch time value back to std::tm structure you can use either of std::localtime and std::gmtime functions from <ctime> header. And finally, if you want to convert std::tm to string, there is an analogous manipulator std::put_time which is used with output stream's operator<<.

Thanks for reading, I hope some people will use this approach when they encounter the same problem.

Thinking about undo/redo

    Hi there, this time I want to share some thought about how one can provide undo/redo support in his application. First of all, let's try to figure out what undo or redo means from programmer's perspective. There can be two approaches. First, the classes responsible for the application or a part of it always have some state (usually this is the set of data members), and undo is just a transition from one state to the previous one, and redo, respectively, from a state to the next one. Do not confuse the next one with something that will happen in the future, because redo only becomes available after at least one undo, so redo itself can be viewed as an undo after another undo. Anyway, everyone knows this part fine, because this is supported by most of the applications, especially by those providing a graphical user interface.

    The other case is when the importance is handed to the actions and not to the objects owning the state, so for example on the Document object the insertion (typing) or deletion of a text can be undoable, but for the same Document the resize operation can be not undoable at all. As you can see, the notion of state is not so relevant here, because having two consecutive states we cannot say for sure (for some cases we can, but this will take some more effort which is redundant) which action or what group of actions is responsible for that transition. So this is the second approach - the action itself may be undoable or not.

    What is interesting, if we think further, the action cannot handle such a big responsibility itself. Let's consider the same example, how can the delete action (button, or a menu item) undo itself? Undo means taking back all the changes that were caused by the action. These changes were caused to the Document, more precisely to the state of Document. It means delete has so much access to Document that it can change its state (some string member for example, or a shape object). To be able to undo these changes, delete action should have similar level of access to another behavior for restoring the Document's state. Thus, we again end up with the notion of state, but there is still a huge difference between two approaches. Let me give some real-world examples before I proceed to details.

    Suppose there is a gallery in the center of a city and masterpieces of famous artists are presented there. And you've been visiting the gallery very often during last 5 years, so you have seen all the works, and there is nothing new for you. But one day there is an announcement of an exhibition of a new young artist. You go and see all his paintings or drawings instead of the old usual ones. But after five days, the exhibition ends and the masterpieces are again hung in their usual places. So this is an example of the first approach. The state (original masterpieces) was saved somewhere in the basement, and then it was restored.

    For the second case, suppose your car is parked near the curb in some 20 meters from the traffic light. Then you drive forward 10 meters, and you remember that you've forgotten something, and you put the gear on rear and drive back these 10 meters and park at the same exact place. So now in terms of position your car is in the same place as before, so we can say that the drive action was undone, but the state of the car is not the same, the oil in the engine was still and now you just turned the ignition off and the oil has not manage to come down yet, the engine is a little warmer, the fuel in the tank is a little lesser, and so on.

Let me give two more examples, software related, and then we can go ahead. For first case - imagine you are filling some online form to send to the immigration services, but the form is too long, so there is a button called 'Save Draft' which saves the current state of the form, and then you can close your browser, come back any time later, log in to the same page and continue from where you stopped. In this example, the state is just the set of values of form fields you are filling (most likely all the fields are unique, so the values cannot be derived from each other). You can say "where is undo here". Undo is when not actually a supported operation for this case, but if you save the draft then continue filling the form, and suddenly the electricity goes off, after that you open the browser and actually the changes are undone to the previous state.

    For the second case - imagine a huge 3d graphical editing tool like Autocad or CorelDraw, and you start stretching some line, but your hand is not accurate enough and you move the mouse a little more than necessary, so the line becomes longer than you need. There are thousands of other objects in the same document you are editing, so you click undo, and the stretch action is undone. It is easier to stretch the single line back, than to store all the thousands of objects to restore the state.

    OK, enough fairy tales, now let's use some programming. If you don't mind I will start with the last two examples. So now I want to support the save draft action for the online form. I think everyone can do that:

class OnlineForm

{

public:

       void load(); // loads the form with the saved data if available

       void saveDraft() const; // saves the current state of the form

       void submit() const; // submits the form data to the server

       void clear(); // clears all the fields of the form

private:

       // form data

       int id;

       int phone;

       string name;

       string address;

       // ... and so on

};

saveDraft can save the filled data in an .xml file, for example, or in a database, and load will read and fill the form from the same place. Now if we want to support undo we need to be able to save the state as many times as needed and store these snapshots separately. And if we know the snapshot corresponding to current state, then undo is only a call to load with the previous snapshot, and redo is a call to load with the next snapshot provided as an argument. It is, of course, preferable to have two member functions getSnapshot and setSnapshot (or, which is more conventional, getState and setState) which will respectively retrieve and set the state of the form. Besides this, we better encapsulate the state into another class, this will keep things more decoupled and the function prototypes more brief. Let's call this class FormData. As I already mentioned load should be replaced by setState, which will accept an instance of FormData, so that the original source of our data (.xml, database, etc.) is not hard-coded in the OnlineForm class, but is defined as a serialization/deserialization of FormData. This will also make it easy to change the source, simply introducing a new serializer class for FormData.
    Also, we don't need saveDraft() anymore, we need getState() which will return the current state of the form within a FormData instance. So now our code will look like this:

struct FormData

{

       // form data

       int id;

       int phone;

       string name;

       string address;

       // ... and so on

};

class OnlineForm

{

public:

       FormData getState() const; // replaces saveDraft with
                                  // a better functionality

       void setState(const FormData& newState); // restores the state

       void submit() const; // submits the form data to the server

       void clear(); // clears all the fields of the form

private:

       FormData state;

};

    To support undo and redo for the OnlineForm, we need to have some convention on what we assume an undoable action. It can be a single character append in a textbox, or it can be a single field update (textbox, checkbox, combobox, etc.), or it can even be an update of a group of related fields (Personal info, job details, address, payment method, etc.). After each of this conventional action(s) we will call the getState and store the state in some place, and we always should keep track of the current state.

class OnlineForm

{

public:

       FormData getState() const

       {

              return states[currentStateIndex];

       }

       void setFirstName(const string& name)

       {

              FormData newState = getState();

              newState.name = name;

              setState(newState);

       }

       void undo()

       {

              if (currentStateIndex > 0)

              {

                     --currentStateIndex;

                     // probably, we should have some function call here,

                     // to refresh the form view, so that the correct data

                     // appears in the fields. And the "correct" data is

                     // the one retrieved by getState() call.

              } else {

                     // We are in the initial step and cannot undo,

                     // we can throw an exception, or for a better UX

                     // we can just disable undo button at all when

                     // this condition (else case) becomes effective.

              }

       }

       void redo(); // almost the same code as for undo().

private:

       void setState(const FormData& newState)

       {

              states.push_back(newState);

              ++currentStateIndex;

       }

       vector<FormData> states;

       int currentStateIndex;

};

I moved setState() declaration to the private section, because any intervention from outside would break the undo logic, now each separate action, like setFirstName will call setState. So generally, we have the undo/redo logic working, but within a bad implementation, most likely we should have an interface with undo() and redo() pure virtual functions, and it can be a generic one of the state object type - in our example FormData. Also, the OnlineForm itself may not be responsible for storing the states - instances of FormData, so we may need the third class responsible for the storage. If you remember this comes to the memento pattern described in GOF Design Patterns book. One more good thing we can do, make undo/redo accept an integer of how many steps we want to go back/forth. So there are many details which mainly depend on the exact application we write. But the general idea is the one already described:

• have a strictly defined state, which most likely does not contain all the data members of the class in the question (in our example state does not have currentStateIndex, etc.);
• after each undoable step, make another snapshot of your object, i.e., store a new instance of state;
• track the current state in your list of states so that you can go back and forth whenever needed (needed here means, for example, pressing undo/redo button on the UI).

So what bad things can arise here, what are the pitfalls of this approach? Suppose the state does not consist of some primitive objects like int or string (string also can be dangerous, the reason is coming soon), but it has some internal data structures, for example an object graph. We cannot easily copy the whole state every time we do some undoable action, because, first, the state can be huge in size, and keeping many instances of state will fill the memory very soon. Second, we need a deep copy for storing the state, we cannot just keep the address of the root node of the graph and restore it from that address. In some cases, we can implement some kind of simple compression, for example, we can store only the difference between previous and current states, not the whole state, more precisely, store only the fields which have been changed. But this will introduce some more complexities in code. Also this still does not solve the deep copy problem. That's when the second approach of implementing undo/redo comes to a stage.

    In second approach, as I have already mentioned, we do not need to keep any state, but the actions that we want to be undoable, have to have some more logic. Let's take the same example of a graphical editor. There are several actions like stretch a line, fill the shape, etc. First, each action has some execute() function, which incorporates the logic of the action itself. Now we want to add an undo() function, which will work at least so well as execute does. For simplicity I will not focus on making the code generic, so I will present some specific actions for specific targets (always referring to the examples already brought up). Here are our actions for stretching a line and filling the shape with some color:

class StretchAction

{

public:

       void setLength(double length);

       void execute(Line line);

private:

       double length;

};

class FillAction

{

public:

       void setColor(Color color);

       void execute(Shape shape);

private:

       Color color;

};

Let's think about how to support undo. We need to keep the history of executed actions, so that each time we press undo in the editor it retrieves the current item and calls undo() on it. This means that each action should have some small amount of history also, to know how to revert things back. For stretch action we can have the previous (one that was before stretching) position of the line, uniquely defined by its endpoints, for example. For the fill action, we have no other way than keeping the old color. So we can change our actions a little bit and get the following version:

class StretchAction

{

public:

       void setLength(double length);

       void execute(Line line);

       void undo(Line line)

       {

              line.moveTo(oldP1, oldP2);

       }

private:

       double length;

       Point oldP1, oldP2;

};

class FillAction

{

public:

       void setColor(Color color);

       void execute(Shape shape);

       void undo(Shape shape)

       {

              shape.fill(oldColor);

       }

private:

       Color color;

       Color oldColor;

};

You probably have many questions now, and I will try to answer all of them, well, all that I can think of.

• How do we know which Line or Shape object to pass to undo()? - I assume that the worksheet itself supports this functionality, e.g., current selection, active object, etc. If not, we could make the action to execute on the worksheet itself and also remember the Line object also which it operated on. But in this case we would have to worry about some synchronization stuff, for example when we delete a shape from the worksheet and then undo, the address of the new object is not necessarily the same, so we should think of some complicated way of referring to the worksheet objects.
• How do we know that the object acted upon will always support the operations implied by undo? - As we can see, doing something and undoing that change do not always invoke the same function of the object acted upon. But most likely if we are the author of undo/redo support, we also have a change access to the source code for the classes for which we are implementing that support. I mean we can add the missing pieces of behavior.
• What do we store in the undo history? - We can store instances of the actions themselves, though we would need to make an abstract base Action (see Command design pattern) which would be the parameter type of the history container. In case of my example I hardly can find a more efficient way of retaining the history, because we would still need to know the original and target values (color or pair of endpoints) and we still would need to know which action was applied, so at least some 4 bytes again. But this is exactly the case now - we have the values and vptr (I am considering that you are not reluctant and have already created the base abstract Action) for each instance of class which is again 4 bytes (for 32-bit systems).
• How to implement redo() then? - Well, redo() will be just a single call of execute() on the same object.
• Who should keep the history? - Most probably the editor, or if it supports multiple worksheets, it may be the worksheet, it depends on your business logic, so this is not always the same.

For some actions you may not even need to store additional data for undo support. Remember my example of driving the car. So if you keep the distance passed during driving, then driving back will need exactly the same distance, nothing more (well you may keep the route also, to know when and where to turn, but this is again the data required for driving forward, so no additional cost for backing up).

    This was the idea of the second approach, each action is responsible for reverting the changes done by itself. Both of these approaches share some common thing - they keep the old state to be able to restore it later. This is actually the essence of undo, without knowing what was before, we cannot go back to that state, and no one can do that, so do not think of any new ways of implementing undo, without having information about the state which you want to go back to.

I did not bring up the complete code and even not a well-defined piece of code, it was just some mock-up to make the comprehension easier and faster. And I put the title "Thinking about..." not "Implementing...", so don't blame me. I believe there are still open questions, but I don't have much time to cover everything, and everything in my understanding differs from what you think of it. Please post your questions in the comments, and I will be happy to answer. Thanks for reading.