diff options
Diffstat (limited to 'SrcShared/EmMinimize.cpp')
| -rw-r--r-- | SrcShared/EmMinimize.cpp | 1310 |
1 files changed, 1310 insertions, 0 deletions
diff --git a/SrcShared/EmMinimize.cpp b/SrcShared/EmMinimize.cpp new file mode 100644 index 0000000..16ce4e6 --- /dev/null +++ b/SrcShared/EmMinimize.cpp @@ -0,0 +1,1310 @@ +/* -*- mode: C++; tab-width: 4 -*- */ +/* ===================================================================== *\ + Copyright (c) 2001 Palm, Inc. or its subsidiaries. + All rights reserved. + + This file is part of the Palm OS Emulator. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. +\* ===================================================================== */ + +#include "EmCommon.h" +#include "EmMinimize.h" + +#include "EmApplication.h" // gApplication->ScheduleQuit +#include "EmDlg.h" // MinimizeProgressOpen, DoCommonDialog +#include "EmEventPlayback.h" // EnableEvents, DisableEvents +#include "EmPalmOS.h" // EmPalmOS::GenerateStackCrawl +#include "EmSession.h" // gSession +#include "Logging.h" // LogAppendMsg +#include "ROMStubs.h" // DmDatabaseInfo +#include "Startup.h" // Startup::MinimizeQuitWhenDone +#include "EmEventOutput.h" // StartGatheringInfo, GatherInfo, OutputEvents + +#include "ChunkFile.h" // ChunkFile +#include "EmStreamFile.h" // EmStreamFile +#include "SessionFile.h" // SessionFile + +#include <math.h> // pow +#include <strstream> // strstream + +/* + Minimization Overview + + A Gremlin run may terminate in error after any number of events. + However, experience has shown that not all events created by the + Gremlin are necessary to reproduce the error. Through minimization, + the Palm OS Emulator attempts to find the minimal set of events that + will cause an error. The use of "an" rather than "the" is + intentional, as we can have no assurance that any error that occurs + when intermediate events are cut out is the same error that + initially occurred. The distinction is likely academic; what matters + is that, given a file describing events that were generated by a + Gremlin during a run, minimization will separate the wheat from the + chaff, so to speak, by cutting out those events that do not + contribute to the error. + + Theory + + Each event generated by a Gremlin can be viewed as a vertex in a + directed graph. Each of these events relies on a particular context + for its action to be relevant. For example, the first event relies + on the root state to be loaded, and nothing else. The vertex or + vertices that are responsible for bringing about a context (such as + bringing up the Find dialog) have directed edges to all vertices + representing actions within this context. If a particular vertex + relies on no prior vertices for its context (the first vertex being + a prime example), then the only vertex with an edge to it is the + vertex representing the root state, which is noteworthy because it + is the only vertex with no incoming edges. + + Viewed in this way, it becomes apparent that the problem of + minimization is nothing more than finding the minimal set of + vertices such that there is an unbroken string of directed edges + between said vertices, and that the vertices representing the root + state and the error-causing event are both within this set. + + In an alternate interpretation, events are once again vertices, and + there are causal directed edges between events; the difference lies + in that an edge is present iff the events represented by its + endpoints are necessary to cause the error. Then the problem of + minmization becomes a vertex cover problem: for reference, see: + <http://www.cs.sunysb.edu/~algorith/files/vertex-cover.shtml>. + + Algorithm choice + + Vertex cover is an NP-complete problem, so it is not surprising that + we cannot find a polynomial-time (in the number of events) algorithm + to find the minimal set of events that will cause an error. Instead, + I settle for an algorithm of order O(n^2 log n) -- in the worst + case, it may have to make n log n passes, each O(n) because there + are n events. This algorithm, while superficially resembling a + divide-and-conquer algorithm, really is just a blind uninformed + search algorithm that happens to narrow its scope by a factor of 2 + each time that it cuts out too many events. (Incidentally, I + implemented a true divide-and-conquer algorithm as well, of nominal + complexity O(n log n), which turned out to be slower on average than + this algorithm, because of the sparse nature of this problem space + since relatively few events typically contribute to an error.) + + Initially, the algorithm sub-divides the original event ranges into + two or more smaller ranges, each range smaller than some hard- coded + value (1024 in this implementation). Each range is then considered + one at a time by. The range is cast out, and then the remaining + events are replayed to see if the crash still occurs. If not, then + the "cast out" range is considered non-essential and is permanently + removed. If the error no longer occurs, then some event is that + range is considered crucial to producing the crash. The range is the + sub-divided in an effort to narrow in on which event or events are + required. Sub-division continues to the single event level. + + After each of the initial sub-disivisions has been examined in this + fashion, Poser checks to see if any events have been permanently + removed. If so, the remaining set of events is saved to their own + .pev file, and the process begins again with this reduced set of + events. Minimization proceeds with this iteration until it has a + set of events it can no longer reduce. + + Implementation + + Since the structure of Palm OS Emulator does not allow for a + recursive function that controls the entire process of minimization + (as would ideally be the case), more novel means are used instead. + As noted in the example below, the minimization process works by + taking an event range, splitting it in two, and then testing each + side to see if it is necessary for an error to occur. If so, then + we permanently disable that range of events and try the other half. + But if the error did not occur, then we need to split the sub-range + in two again and try again. + + The state for the process of splitting event ranges is stored in the + fgState member. This variable contains an fLevels member, which is + a stack of event ranges. The oldest item on the stack contains the + entire event range. The next items on the stack contain the left + and right ranges after bisecting the initial range. Each subsequent + element on the stack is a further splitting of a range of the + previous element. + + Example + + Let us imagine that we have a 8-event Gremlin run that terminates in + an error that we wish to minimize. Of these 8 events, numbered + 0-indexed from 0-7, only events 0 and 7 are necessary. What these + events actually are is inconsequential. + + This is the sequence of events that would transpire: + + LoadEvents would load the .pev file, initializing the event history + vector. In Start, an initial event range, whose span is the whole + range of events (0-7) would be created. Since I make the (relatively + safe) assumption that one cannot eliminate all of the events in a + Gremlin run (save for the penultimate and ultimate events) and still + hope to encounter the error, the root range's events are not turned + off, and instead it spawns two sub-ranges. These two child ranges + cover the ranges (0-3) and (4-7), respectively. First the (0-3) + range would be selected (this in Start -- for all other selections, + NextSubRange is the locale), and events 0-3 turned off by setting + appropriate bits in a mask to false. The mask at this point would + look like this: f-f-f-f-t-t-t-t. Since event 0 is necessary to + reproduce the error, we would reach NoErrorOccurred. This means + that we now knew that something in the range (0-3) was important, + and that we needed to further examine that range. Thus, we end up + calling SplitAndStartAgain. + + In NoErrorOccurred, (0-3) would have its events turned on, and then + SplitAndStartAgain would sub-divide the range into (0-1) and (2-3). + The event mask of (0-1) would then be masked (ie, the events would + not be replayed). At this point the event mask would look like this: + f-f-t-t-t-t-t-t. Again, we would not find the error, since event 0 + would still not be replayed. The process would then be repeated, + with the ramge (0-1) spawning two sub-ranges of (0-0) and (1-1). The + left child of (0-1), (0-0) would be selected to run next. The event + mask would look like this: f-t-t-t-t-t-t-t. + + This time, since we would be playing back all events except for 0, + the run would again not terminate in error. At this point we will + have hit our depth limit, so in NoErrorOccurred, the events in the + current range (only event 0) would be turned on. Then, in + SplitAndStartAgain, we would realize that we could no longer split + the event range. We would then call NextSubRange, which would + select (1-1) from the stack of event ranges still left to examine. + The event mask at this point would look like this: t-f-t-t-t-t-t-t. + Its run would terminate in error, so from + ErrorHandling::HandleDialog, ErrorOccurred would be called, not + NoErrorOccurred. This means that the range (1-1) will not spawn + children of its own, or have the events within its range turned back + on. Instead, ErrorOccurred will climb up the stack to (2-3). Its + events would be turned off, making the event mask look like this: + t-f-f-f-t-t-t-t. + + Since events 0 and 7 are both turned on, this run would terminate in + error. In ErrorOccurred, event range (4-7) would be the next set of + events to examine. When (4-7)'s events are turned off, event 7 would + be turned off, and the error would no longer occur. The process + would then continue until events 0 and 7 were the only events + remaining, where the event mask is t-f-f-f-f-f-f-t. This run would + terminate in error, since events 0 and 7 would be played back. + + In ErrorOccurred, we'd see that the event range stack would be + exhausted. We'd then save out the remaining events (0 and 7) to a + .pev file and run the whole process over again to see if any further + progress could be made. In our hypothetical situation, we'd find + that events 0 and 7 would still be needed. + + Next, we would make one last pass over the remaining events. This + time, it's not to see if any events can be removed. Instead, it's + to collect contextual information useful in creating an English + report for the user. In particular, we'd find out what, if any + objects on the screen were hit by pen events so that we could report + then instead of telling the user to tap at, say, screen location 53, + 112. + + Finally, the ultimate minimal set of events is written to a .pev + file suitable for replaying, and are are converted into a set of + English instructions that, when followed by a human, should result + in the same crash as replaying the events file does. + + Improvements + + The current algorithm, while useful, could still be improved in many + ways. Following are some ideas that occur to us, in case some + developer feels the need to implement them for us. :-) + + * Semantic subdivision + + Currently, the algorithm makes little distinction as to where it + decides to sub-divide event ranges. Other than the initial set of + ranges (where Poser keeps dividing until each sub-range is fewer + than some fairly arbitrary upper limit) and the single-event ranges + (where Poser gives pen-up events special treatment), Poser merely + takes an event range and divides it in two. + + Instead, it would be good to first scope out the set of events and + mark out good division points. At the first level, Poser would find + all places where application switches take place and set division + points at those events. The theory here is that if the Address Book + crashes, what previously occurred in the Calculator application is + of little consequence. A pass over the events would then be made, + attempting to cast out events that occur between app switch events. + + Next, the algorithm would attempt the same thing with forms. Again, + the theory is that if you crash in Form B, what just occurred in + Form A has a good chance of being irrelevent. Of course, this is + not a universally true statement, but that's why we perform our + tests and see what happens. For the cases where Forms A and B are + not strongly connected, we can cut out a whole swath of events at + one blow. + + Next, we examine events at a key and pen sequence level. For key + sequences, we assume that there's little difference between one key + event and many key events. Therefore, we trim down any key + sequences to just the first key and try a run with just that event. + If the crash still occurs, we've just made a big win. Similarly, + with pen sequences, if there are three or more pen-down events + before the final pen-up event, we can try to remove all events + between the first and last pen down events. The idea here is that + only the initial pen down location and the final pen up location are + likely to be important, and that cutting out everything in between + would probably be OK. + + Finally, we can make a pass using the current algorithm that slices + and dices down to the single event level. At this point, we + probably won't be removing too many events, but should also have + relatively few, so the slice and dice process shouldn't take very + long. + + * Menu descriptions + + Currently, taps on menu items are reported as "Tap at x,y". Where + possibly, this is annotated with the name of the dialog that is + brought up because of that menu selection. But it would ultimately + be better to provide the text of the menu and menu item. + + * HTML output + + Currently, the English translation is provided in a plain text file. + What might be nicer is an HTML file that can reference screen shots + showing what's going on at particular points. For instance, + sometimes saying "Tap on control "Foo"" is not enough -- sometimes + it's important to know where on "Foo" was tapped if it were a + multipart control. Being able to see a screen shot with cross-hairs + at the point where the user is supposed to tap would be a big help. + + * Tap-drag + + A sequence of pen-down events followed by a pen-up event are + currently reported as a series of "Tap at x,y" messages. Instead, + they should be reported as "Tap at x,y", "Drag to x,y", etc. + messages. +*/ + + +#if _DEBUG +#define LOG_MINIMIZATION 1 +#else +#define LOG_MINIMIZATION 0 +#endif + +#define PRINTF if (!LOG_MINIMIZATION) ; else LogAppendMsg + +static const int kMaxRange = 1024; // Don't handle any ranges larger than this. +static const int kLastPass = 0; // Indicates we're making a last pass + +omni_mutex EmMinimize::fgMutex; +EmMinimize::EmMinimizeState EmMinimize::fgState; +Bool EmMinimize::fgIsOn; +uint32 EmMinimize::fgStartTime; +long EmMinimize::fgInitialNumberOfEvents; +long EmMinimize::fgDiscardedNumberOfEvents; +long EmMinimize::fgPassNumber; +Bool EmMinimize::fgPassEndedInError; +StringList EmMinimize::fgLastStackCrawl; + + +static inline Bool PrvIsPenUp (const PointType& pt) +{ + return (pt.x == -1) && (pt.y == -1); +} + +static inline Bool PrvIsPenDown (const PointType& pt) +{ + return !::PrvIsPenUp (pt); +} + + +#pragma mark - + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Initialize +// --------------------------------------------------------------------------- + +void EmMinimize::Initialize (void) +{ +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Reset +// --------------------------------------------------------------------------- + +void EmMinimize::Reset (void) +{ + EmMinimize::TurnOn (false); + fgState.fLevels.clear (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Save +// --------------------------------------------------------------------------- + +void EmMinimize::Save (SessionFile&) +{ +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Load +// --------------------------------------------------------------------------- + +void EmMinimize::Load (SessionFile&) +{ +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Dispose +// --------------------------------------------------------------------------- + +void EmMinimize::Dispose (void) +{ + EmMinimize::TurnOn (false); + fgState.fLevels.clear (); +} + + +#pragma mark - + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Start +// --------------------------------------------------------------------------- +// Startup the entire minimization process. Called after a document is loaded +// with the intent of minimizaing the events stored with it. + +void EmMinimize::Start (void) +{ + // Load the events. Events are not loaded by default when the rest of + // the session loads. See comments for EmEventPlayback::Load (). + + EmMinimize::LoadEvents (); + + // Enable all events + + EmEventPlayback::EnableEvents (); + + // Check that this is a stream that ended in error. + + fgInitialNumberOfEvents = EmMinimize::FindFirstError (); + if (fgInitialNumberOfEvents < 0) + { + EmDlg::DoCommonDialog ("Could not find an error.", kDlgFlags_OK); + return; + } + + // Get rid of the error event and all events after it. The error event + // will be returned at the end of the minimization process, but for now, + // it just get's in the way. + + EmEventPlayback::DisableEvents (fgInitialNumberOfEvents); + EmEventPlayback::CullEvents (); + + // Re-update fgInitialNumberOfEvents; the number of events could have been + // decreased further than expected if there were consecutive pen-up events + // in the stream (Gremlins *can* generate that). + + fgInitialNumberOfEvents = EmEventPlayback::CountNumEvents (); + + // Initialize the minimization routines. + + fgState.fLevels.clear (); + fgStartTime = Platform::GetMilliseconds (); + fgDiscardedNumberOfEvents = 0; + fgPassNumber = 1; + + EmMinimize::TurnOn (true); + EmMinimize::InitialLevel (); + EmMinimize::SplitAndStartAgain (); + + // Open the progress dialog. + + EmDlg::MinimizeProgressOpen (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::Stop +// --------------------------------------------------------------------------- +// Stop the entire minimization process. Called when the user presses the +// "Stop" button in the Minimization Control dialog. + +void EmMinimize::Stop (void) +{ + EmMinimize::TurnOn (false); + EmEventPlayback::ReplayEvents (false); + EmEventOutput::GatherInfo (false); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::TurnOn +// --------------------------------------------------------------------------- + +void EmMinimize::TurnOn (Bool newState) +{ + fgIsOn = newState; +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::IsOn +// --------------------------------------------------------------------------- + +Bool EmMinimize::IsOn (void) +{ + return fgIsOn /* && EmEventPlayBack::ReplayingEvents () ? */; +} + + +#pragma mark - + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::NoErrorOccurred +// --------------------------------------------------------------------------- +// The current set of events were replayed with no error occurring. +// Therefore, we need to turn the most recent set of events back on, split +// it, and try again. + +void EmMinimize::NoErrorOccurred (void) +{ + PRINTF ("EmMinimize::NoErrorOccurred:"); + + fgPassEndedInError = false; + + // Turn current set of events back on. + + long begin, end; + EmMinimize::CurrentRange (begin, end); + PRINTF ("EmMinimize::NoErrorOccurred: re-enabling events %ld - %ld.", begin, end - 1); + + EmEventPlayback::EnableEvents (begin, end); + + // If we were doing the "last pass" and got here anyway, we're pretty + // messed up. The "last pass" was supposed to be guaranteed to end in an + // error, but it didn't. Oh well. Finish up and tell the user what + // happened as best as we can. + + if (EmMinimize::fgPassNumber == kLastPass) + { + fgState.fLevels.clear (); + EmMinimize::MinimizationPassComplete (); + return; + } + + // Set the bit that says we examined this range and found it interesting. + + fgState.fLevels.back ().fChecked = true; + + // Split the current range and try again. + + EmMinimize::SplitAndStartAgain (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::ErrorOccurred +// --------------------------------------------------------------------------- +// The current set of events resulted in an error occurring. Therefore, we +// can keep the current set of events turned off, and try to find others to +// turn off. + +void EmMinimize::ErrorOccurred (void) +{ + PRINTF ("EmMinimize::ErrorOccurred:"); + + fgPassEndedInError = true; + + // Capture the current stack crawl in case we need it when reporting + // failure on the last pass to produce an error. + + EmMinimize::GenerateStackCrawl (fgLastStackCrawl); + + // Keep the current set of events turned off. + + long begin, end; + EmMinimize::CurrentRange (begin, end); + PRINTF ("EmMinimize::ErrorOccurred: discarding events %ld - %ld.", begin, end - 1); + + // Update the number of events we've discarded. Note that we update this + // value by calling CountEnabledEvents instead of adjusting by (end - + // begin). That's because some events are not discarded even though we've + // asked them to because they are too important to discard (e.g. pen up + // events). + + fgDiscardedNumberOfEvents = fgInitialNumberOfEvents - EmEventPlayback::CountEnabledEvents (); + + // If the error occurred before the last event was played, then let's + // disable all subsequent events and start afresh. + + long currentEvent = EmEventPlayback::GetCurrentEvent (); + long numEvents = EmEventPlayback::GetNumEvents (); + + if (currentEvent < numEvents) + { + PRINTF ("EmMinimize::ErrorOccurred: error occurred at event %ld of %ld.", + currentEvent, numEvents); + + omni_mutex_lock lock (fgMutex); + + // Disable all events past the one that just caused the error. + + EmEventPlayback::DisableEvents (currentEvent); + + // Clear the event range stack so that we can start a new pass. + + fgState.fLevels.clear (); + + // Start a new pass. This will also cull the events we just disabled. + + EmMinimize::MinimizationPassComplete (); + + return; + } + + // Pop the current range and try the next one. + + EmMinimize::NextSubRange (); +} + + +#pragma mark - + +uint32 EmMinimize::GetPassNumber (void) +{ + return fgPassNumber; +} + + +uint32 EmMinimize::GetElapsedTime (void) +{ + return Platform::GetMilliseconds () - fgStartTime; +} + + +void EmMinimize::GetCurrentRange (uint32& ubegin, uint32& uend) +{ + long begin, end; + EmMinimize::CurrentRange (begin, end); + + ubegin = begin; + uend = end; +} + + +uint32 EmMinimize::GetNumDiscardedEvents (void) +{ + return fgDiscardedNumberOfEvents; +} + + +uint32 EmMinimize::GetNumInitialEvents (void) +{ + return fgInitialNumberOfEvents; +} + + +#pragma mark - + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::MinimizationPassComplete +// --------------------------------------------------------------------------- +// We've finished splitting and replaying events. Examine the results to see +// if we're done, or if we need to make another Minimization passing using the +// remaining events. + +void EmMinimize::MinimizationPassComplete (void) +{ + // Get the initial number of events, remove the masked-out events, and + // then get the remaining number of events. + + long oldNumEvents = EmEventPlayback::GetNumEvents (); + + EmEventPlayback::CullEvents (); + + long newNumEvents = EmEventPlayback::GetNumEvents (); + + // If significant culling occurred, then let's make another pass. + + if (EmMinimize::MakeAnotherPass (oldNumEvents, newNumEvents)) + { + PRINTF ("EmMinimize::MinimizationPassComplete: making another pass."); + PRINTF (" oldNumEvents = %ld", oldNumEvents); + PRINTF (" newNumEvents = %ld", newNumEvents); + + ++fgPassNumber; + + EmMinimize::InitialLevel (); + EmMinimize::SplitAndStartAgain (); + } + + // Make a final pass in order to collect context information + + else if (fgPassNumber != kLastPass) + { + PRINTF ("EmMinimize::MinimizationPassComplete: making last pass."); + PRINTF (" oldNumEvents = %ld", oldNumEvents); + PRINTF (" newNumEvents = %ld", newNumEvents); + + fgPassNumber = kLastPass; + + // Tell EmEventOutput to wake up and start paying attention. + + EmEventOutput::StartGatheringInfo (); + + EmMinimize::InitialLevel (); + EmMinimize::StartAgain (); + } + + // Otherwise, we are done! + + else + { + PRINTF ("EmMinimize::MinimizationPassComplete: DONE."); + PRINTF (" oldNumEvents = %ld", oldNumEvents); + PRINTF (" newNumEvents = %ld", newNumEvents); + + EmMinimize::MinimizationComplete (); + } +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::MinimizationComplete +// --------------------------------------------------------------------------- +// Minimization is completely done. Save the results, write out a text +// version of the events, and tell the user. + +void EmMinimize::MinimizationComplete (void) +{ + PRINTF ("EmMinimize::MinimizationComplete: DONE."); + + // Stop the presses. + + EmMinimize::TurnOn (false); + EmEventPlayback::ReplayEvents (false); + EmEventOutput::GatherInfo (false); + + // Save the minimal set of events. + + EmMinimize::SaveMinimalEvents (); + + // Convert the events to an English description. + + EmMinimize::OutputEventsAsEnglish (); + + // Reset to our initial state (as opposed to the error state we're + // currently in). + + EmMinimize::LoadInitialState (); + + if (Startup::MinimizeQuitWhenDone ()) + { + gApplication->ScheduleQuit (); + } + else + { + // Show a dialog telling the user about the results. + + char buffer[200]; + sprintf (buffer, "Minimization has been completed. %ld of %ld events discarded.", + fgDiscardedNumberOfEvents, fgInitialNumberOfEvents); + + EmDlg::DoCommonDialog (buffer, kDlgFlags_OK); + } +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::SaveMinimalEvents +// --------------------------------------------------------------------------- + +void EmMinimize::SaveMinimalEvents (void) +{ + // Get the original event file. We'll save the events in the same + // directory but with a modified name. + + EmFileRef oldEventRef = gSession->GetFile (); + string oldEventName = oldEventRef.GetName (); + + // Convert the name from <Foo>.pev to <Foo>_Min.pev. + + string newEventName = oldEventName; + + if (::EndsWith (newEventName.c_str (), ".pev")) + { + newEventName = newEventName.substr (0, newEventName.size () - 4); + } + + newEventName += "_Min.pev"; + + // Copy the old session file to the new one that will hold the minimized + // event set. + + EmFileRef newEventRef (oldEventRef.GetParent (), newEventName); + + EmStreamFile oldEventStream (oldEventRef, kOpenExistingForRead, + kFileCreatorEmulator, kFileTypeEvents); + EmStreamFile newEventStream (newEventRef, kCreateOrEraseForWrite, + kFileCreatorEmulator, kFileTypeEvents); + + ChunkFile oldEventChunkFile (oldEventStream); + ChunkFile newEventChunkFile (newEventStream); + + int index = 0; + ChunkFile::Tag tag; + Chunk chunk; + + while (oldEventChunkFile.ReadChunk (index, tag, chunk)) + { + // Copy all chunks except the previous (pre-minimized) event set. + // We'll be adding the minimized event set to the file later. + + if (tag != /*SessionFile::kGremlinHistory*/ 'hist') + { + newEventChunkFile.WriteChunk (tag, chunk); + } + + ++index; + } + + // When starting minimization, we removed all events beyond and including + // the terminating error event. Before saving out the new event set, add + // back the error event. + + EmEventPlayback::RecordEvents (true); + EmEventPlayback::RecordErrorEvent (); + EmEventPlayback::RecordEvents (false); + + // Now write the final event set. + + SessionFile newEventSessionFile (newEventChunkFile); + EmEventPlayback::SaveEvents (newEventSessionFile); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::OutputEventsAsEnglish +// --------------------------------------------------------------------------- + +void EmMinimize::OutputEventsAsEnglish (void) +{ + EmEventPlayback::LogEvents (); + + // Create a string stream to which we will write out results. After we + // completely buffer the output, we'll write it to a file. We don't write + // directly to the file so that we can take advantage of the + // integer-to-text conversion facilities of ostream. + + strstream stream; + + // Write out our initial message. + + EmFileRef ref = gSession->GetFile (); + string path = ref.GetFullPath (); + + stream << "=== Minimal Events: (" << path << ")" << endl; + + // Write out events. + + EmEventOutput::OutputEvents (stream); + + // If the last pass managed to fail to produce an error, tell the user + // about it, and show them the competing stack crawls. + + if (!EmMinimize::fgPassEndedInError) + { + StringList currentStackCrawl; + EmMinimize::GenerateStackCrawl (currentStackCrawl); + + stream << endl; + stream << "WARNING WARNING WARNING" << endl; + stream << endl; + stream << "After the minimization process produces a minimal set of events" << endl; + stream << "leading to a crash, it makes one last run through the events," << endl; + stream << "collecting context information used to create the descriptions" << endl; + stream << "above. However, on this last pass, no error occurred. Following" << endl; + stream << "are the current stack crawl and the stack crawl captured the last" << endl; + stream << "time a crash occurred." << endl; + stream << endl; + + stream << "Current call stack:" << endl; + EmEventOutput::OutputStack (stream, currentStackCrawl); + stream << endl; + + stream << "Last error-producing call stack:" << endl; + EmEventOutput::OutputStack (stream, fgLastStackCrawl); + stream << endl; + } + + // Write out final message. + + stream << "=== Event listing complete." << endl; + + // Get the original event file. We'll save the events in the same + // directory but with a modified name. + + // Convert the name from <Foo>.pev to <Foo>_Min.pev. + + string textEventName = ref.GetName (); + + if (::EndsWith (textEventName.c_str (), ".pev")) + { + textEventName = textEventName.substr (0, textEventName.size () - 4); + } + + textEventName += "_Min.txt"; + + // Create the output file. + + EmFileRef textEventRef (ref.GetParent (), textEventName); + EmStreamFile textEventStream (textEventRef, kCreateOrEraseForWrite | kOpenText, + kFileCreatorCodeWarrior, kFileTypeText); + + // Write the event text to it. + + textEventStream.PutBytes (stream.str (), stream.pcount ()); + + // Unfreeze the stream, or else its storage will be leaked. + + stream.freeze (false); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::MakeAnotherPass +// --------------------------------------------------------------------------- +// Return whether or not we feel that a significant amount of event culling +// had occurred in the pass. If so, we'll want to make another pass. + +Bool EmMinimize::MakeAnotherPass (long oldNumEvents, long newNumEvents) +{ + // Make another pass if we've reduced the number of events in the previous + // pass by more than 10%. + + return newNumEvents < oldNumEvents; +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::CurrentRange +// --------------------------------------------------------------------------- +// Return the current event range that we are examining. + +void EmMinimize::CurrentRange (long& begin, long& end) +{ + omni_mutex_lock lock (fgMutex); + + if (fgState.fLevels.size () > 0) + { + begin = fgState.fLevels.back ().fBegin; + end = fgState.fLevels.back ().fEnd; + } + else + { + begin = 0; + end = 0; + } +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::InitialLevel +// --------------------------------------------------------------------------- +// Set up our "fLevels" member with the initial left/right event sub-ranges. + +void EmMinimize::InitialLevel (void) +{ + EmAssert (fgState.fLevels.size () == 0); + + // Establish the initial event range. + + EmMinimizeLevel newLevel; + + newLevel.fBegin = 0; + newLevel.fEnd = EmEventPlayback::GetNumEvents (); + newLevel.fChecked = false; + + omni_mutex_lock lock (fgMutex); + + fgState.fLevels.push_back (newLevel); + +#if LOG_MINIMIZATION + { + PRINTF ("EmMinimize::InitialLevel: Added first level."); + + EmMinimizeLevelList::iterator iter = fgState.fLevels.begin (); + + while (iter != fgState.fLevels.end ()) + { + PRINTF (" %ld:", iter - fgState.fLevels.begin ()); + PRINTF (" fBegin: %ld", iter->fBegin); + PRINTF (" fEnd: %ld", iter->fEnd); + PRINTF (" fChecked: %s", iter->fChecked ? "TRUE" : "FALSE"); + + ++iter; + } + } +#endif +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::SplitCurrentLevel +// --------------------------------------------------------------------------- +// Create a new level based on the given range. The given range is split in +// two, records are created holding those two sub-ranges, and the records are +// pushed onto our stack. Returns false if it was unable to create the two +// new ranges (either because the current range is too narrow or too deep). + +Bool EmMinimize::SplitCurrentLevel (void) +{ + omni_mutex_lock lock (fgMutex); + + EmAssert (fgState.fLevels.size () > 0); + + // Split the next event range until it's of a manageable size. + + while (1) + { + EmMinimizeLevel prevLevel = fgState.fLevels.back (); + long prevRange = prevLevel.fEnd - prevLevel.fBegin; + + // If we're at the smallest range, leave and say we can't split this + // atom. + + if (prevRange <= 1) + return false; + + // Pop the top event range, split it, and put it back. + + long midpoint = (prevLevel.fBegin + prevLevel.fEnd) / 2; + + EmAssert (prevLevel.fBegin < midpoint); + EmAssert (midpoint < prevLevel.fEnd); + + fgState.fLevels.pop_back (); + + EmMinimizeLevel newLevel; + + newLevel.fBegin = midpoint; + newLevel.fEnd = prevLevel.fEnd; + newLevel.fChecked = prevLevel.fChecked && (newLevel.fEnd - newLevel.fBegin) > 1; + + fgState.fLevels.push_back (newLevel); + + newLevel.fBegin = prevLevel.fBegin; + newLevel.fEnd = midpoint; + newLevel.fChecked = prevLevel.fChecked && (newLevel.fEnd - newLevel.fBegin) > 1; + + fgState.fLevels.push_back (newLevel); + + // If the range is now small enough, leave and say we have new ranges + // to deal with. + + if (newLevel.fEnd - newLevel.fBegin <= kMaxRange) + break; + } + +#if LOG_MINIMIZATION + { + EmMinimizeLevelList::iterator iter = fgState.fLevels.begin (); + + while (iter != fgState.fLevels.end ()) + { + PRINTF (" %ld:", iter - fgState.fLevels.begin ()); + PRINTF (" fBegin: %ld", iter->fBegin); + PRINTF (" fEnd: %ld", iter->fEnd); + PRINTF (" fChecked: %s", iter->fChecked ? "TRUE" : "FALSE"); + + ++iter; + } + } +#endif + + return true; +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::StartAgain +// --------------------------------------------------------------------------- +// Queue things up to start again. Start the playback mechanism, and reload +// the initial state. + +void EmMinimize::StartAgain (void) +{ + PRINTF ("EmMinimize::StartAgain: starting over."); + + EmEventPlayback::ReplayEvents (true); + EmMinimize::LoadInitialState (); + + LogDump (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::SplitAndStartAgain +// --------------------------------------------------------------------------- +// Queue things up to start again. Start the playback mechanism, and reload +// the initial state. + +void EmMinimize::SplitAndStartAgain (void) +{ + // Try to split the range. We may not be able to do that if the range is + // too narrow or we've split too many times already. + + if (EmMinimize::SplitCurrentLevel ()) + { + PRINTF ("EmMinimize::SplitAndStartAgain: split current range."); + + // Attempt to disable the current range and start again. This may + // fail if we try to do something like disable a solitary pen-up + // event, in which case we'll move to the NextSubRange. + + EmMinimize::DisableAndStartAgain (); + } + else + { + // We weren't able to split the current event range. That must mean + // that the event(s) in this range were important, and that we may + // have found the reason that the initial range we started subdivided + // is interesting. Assuming that, clear the fChecked bit on all + // entries on our stack, forcing us to retest them before splitting + // them. + + { + omni_mutex_lock lock (fgMutex); + + EmMinimizeLevelList::iterator iter = fgState.fLevels.begin (); + while (iter != fgState.fLevels.end ()) + { + iter->fChecked = false; + ++iter; + } + } + + // Pop the current range off and work with the next one. + +#if LOG_MINIMIZATION + EmMinimizeLevel level = fgState.fLevels.back (); + + PRINTF ("EmMinimize::SplitAndStartAgain: too deep or narrow -- moving along."); + PRINTF (" begin: %ld", level.fBegin); + PRINTF (" end: %ld", level.fEnd); + PRINTF (" checked: %s", level.fChecked ? "TRUE" : "FALSE"); +#endif + + EmMinimize::NextSubRange (); + } +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::DisableAndStartAgain +// --------------------------------------------------------------------------- +// Attempt to disable the current range and start again. This may fail if we +// try to do something like disable a solitary pen-up event, in which case +// we'll move to the NextSubRange. + +void EmMinimize::DisableAndStartAgain (void) +{ + long begin, end; + EmMinimize::CurrentRange (begin, end); + + PRINTF ("EmMinimize::DisableAndStartAgain: disabling events %ld - %ld.", begin, end - 1); + + // Don't try disabling pen-up events. If the pen-up event is preceded by + // one or more pen-down events, then EmEventPlayback won't let it be + // disabled. If the pen-up event is not preceded by a pen-down event, + // then EmEventPlayback will have already filtered it out. Either way, we + // don't get anything by trying to disable such an event and replaying the + // event stream all over again. + + if (end - begin == 1) + { + EmRecordedEvent event; + EmEventPlayback::GetEvent (begin, event); + + if (event.eType == kRecordedPenEvent && ::PrvIsPenUp (event.penEvent.coords)) + { + PRINTF ("EmMinimize::DisableAndStartAgain: not disabling pen up event."); + NextSubRange (); + return; + } + } + + // Turn off the events in the current sub-range. + + EmEventPlayback::DisableEvents (begin, end); + + // Start again. + + EmMinimize::StartAgain (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::NextSubRange +// --------------------------------------------------------------------------- +// Pop an event range off of the stack and start working with the previous +// range that's now on the top of the stack. + +void EmMinimize::NextSubRange (void) +{ + { + omni_mutex_lock lock (fgMutex); + + PRINTF ("EmMinimize::NextSubRange: popping a level."); + + EmAssert (fgState.fLevels.size () > 0); + + fgState.fLevels.pop_back (); + } + + // If there are no more ranges, we are done with this pass. Check the + // results to see if we'd like to make another pass. + + if (fgState.fLevels.size () == 0) + { + EmMinimize::MinimizationPassComplete (); + return; + } + + // Determine what to do with the range that's now at the top of the stack. + // Either we start testing it directly, or we see if we can skip that + // step and start splitting it. If we guess correctly, we can save a lot + // of time. If we assume we don't have to split this range first, then + // testing it in toto may show that we can get rid of it all right now. + // Otherwise, we'd end up splitting it down to the single event level + // before we discovered we didn't need any of the events. On the other + // hand, if we're fairly sure that we need to closely examine this range, + // we save time by not testing it in toto first, and proceed directly to + // splitting it. + // + // We maintain a Boolean flag that tells us whether or not to test the + // entire range before splitting or to split before testing each half. As + // well, we split any range that is larger than our hardcoded upper limit + // on event ranges. + + EmMinimizeLevel currLevel = fgState.fLevels.back (); + + if (currLevel.fChecked || ((currLevel.fEnd - currLevel.fBegin) > kMaxRange)) + { + EmMinimize::SplitAndStartAgain (); + } + else + { + PRINTF ("EmMinimize::NextSubRange: disabling events %ld - %ld.", + currLevel.fBegin, currLevel.fEnd - 1); + + // Attempt to disable the current range and start again. This may + // fail if we try to do something like disable a solitary pen-up + // event, in which case we'll move to the NextSubRange. + + EmMinimize::DisableAndStartAgain (); + } +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::LoadInitialState +// --------------------------------------------------------------------------- +// Reload the current file so that we can start pelting it with events again. + +void EmMinimize::LoadInitialState (void) +{ + // Queue up a call to RealLoadInitialState. + + gSession->ScheduleMinimizeLoadState (); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::RealLoadInitialState +// --------------------------------------------------------------------------- +// Reload the current file so that we can start pelting it with events again. + +void EmMinimize::RealLoadInitialState (void) +{ + ErrCode result = errNone; + + try + { + EmAssert (gSession); + gSession->Load (gSession->GetFile ()); + + PRINTF ("EmMinimize::RealLoadInitialState: Reloaded initial state."); + } + catch (ErrCode errCode) + { + result = errCode; + } + + // !!! Should probably do something on failure! + +// return result; +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::LoadEvents +// --------------------------------------------------------------------------- + +void EmMinimize::LoadEvents (void) +{ + EmAssert (gSession); + + EmEventPlayback::LoadEvents (gSession->GetFile ()); + + PRINTF ("EmMinimize::LoadEvents: loaded %d events.", EmEventPlayback::GetNumEvents ()); +} + + +// --------------------------------------------------------------------------- +// ¥ EmMinimize::FindFirstError +// --------------------------------------------------------------------------- +// Return the index of the first error event record. Return -1 if one could +// not be found. + +long EmMinimize::FindFirstError (void) +{ + // The actual implementation for this function is over in EmEventPlayback + // for now. The current EmEventPlayback interface and implementation + // doesn't support the efficient retrieval of arbitrary events, so we put + // the whole FindFirstError implementation over there. + + return EmEventPlayback::FindFirstError (); + +/* + EmRecordedEvent event; + long numEvents = EmEventPlayback::GetNumEvents (); + + for (long ii = 0; ii < numEvents; ++ii) + { + EmEventPlayback::GetEvent (ii, event); + + if (event.eType == kRecordedErrorEvent) + { + PRINTF ("EmMinimize::FindFirstError: found an error event."); + return ii; + } + } + + PRINTF ("EmMinimize::FindFirstError: failed to find an error event."); + return -1; +*/ +} + +void EmMinimize::GenerateStackCrawl (StringList& stackCrawl) +{ + // Capture the stack crawl. + + EmStackFrameList stackFrames; + EmPalmOS::GenerateStackCrawl (stackFrames); + + // Generate a full stack crawl. + + ::StackCrawlStrings (stackFrames, stackCrawl); +} |