path: root/SrcShared/EmMinimize.cpp

/* -*- 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);
}