The blowup came up in this very interesting type of OutOfMemory error:
I read wikipedia articles on DFA, NFA, PDA, and grammars. I also had a meeting with Dr. Rodger, and setup CVS version control under the jflap09 directory. I also helped Jonathan with getting the image dumps working, employing a somewhat ugly hack to allow dumping of the image. The hack works as follows:
we need to make the AutomatonPane Displayable, which requires it to be "packed". However, JPanel does not have a "pack" method, so we shove it inside a newly created (but never displayed JFrame) and pack that instead.
Unfortunatly this is a limited hack, so we discussed how we might refactor the Panel Hierarchy with an extra superclass (between JPanel and each of the types of panes) to provide a handle to the AutomatonPane.
This would provide a degree of useability; at least the user would be able to save images of a current tab IFF that tab was not split. Under the same restriction, it also might open up the ability to zoom in on a part of a pane, or make the text and images bigger when the window is resized. This type of functionality could go in the new superclass.
At the end of the day, I started skimming the Linz book.
I spent most of the day reading the Linz book for concepts. I also did a couple of JFLAP tutorials towards the end of the day. I left early today because I needed to get some paperwork done before 5, but I brought the book home to continue reading tonight.
I came in around 9:20 and no one was here yet, so I could not get into the office. I joined Jenna in her office, since she was already there.
As I was reading, I tried constructing figure 2.12 in JFLAP and found a couple of errors which seem specific to linux (I'm running ubuntu). The first error occured when I tried "convert DFA to NFA," did the conversion half way, and then got an error message that was completely blank.When Jonathan tried to replicate it on his computer (he's runnning Windows), the same error did not come up.
I also started working on writing a description of grammars for the tutorial pages. Unfortuntely, when I was about half-way done, I accidentally overwrote the file. I recoverd most of the work from an hourly snapshot, however.
The current tutorial page (still working on is at) available here. I have attempted to write most things out in English, since the book and wikipedia provides enough formal notation for anyone who might want it. Please let me know if you'd prefer me to use more formal notation.
I read about context-free grammars and languages and push-down automata, as well as Turing machines and unrestricted grammars. I learned that Turing's thesis is not proven, although it is well-substantiated, much as Newton's laws of physics are.
Experimenting with JFLAP at the end of the day, I noticed a number of odd things when using JFLAP under Linux. For example, instead of Ctrl-S to save, it says Meta-S. However, none of the standard meta keys seem to produce the desired behavior. I plan to look into that when I look at the source code.
The more I play with JFLAP, the more interesting things I come across. Today, when I had the window maximized and I requested highlight non-determinism, JFLAP zoomed into the image, thus presenting the effect that we were desiring earlier. Jonathan is looking it up in the source.
A new widow will appear showing the traceback of that configuration - From http://jflap.org/tutorial/fa/createfa/fa.html
"it will be tinted a darker shade of purple" (the color is blue) - From http://jflap.org/tutorial/fa/createfa/fa.html
"No Nondterminism" - http://jflap.org/tutorial/mealy/mooreMachines.htmlAlso read about Turing machines.
I spent the day trying to get a complete understanding of the JFLAP source (both for easier coding later and to understand what might break when I try to add Undo functionality), by first looking at the Javadocs and then referring to the source when something was unclear. The following are some notes I made as I was reading:
instanceof calls. I would like to attempt to refactor this by leavivng the common code in Automaton and pushing the uncommon code into the subclasses. Also, I see no reason why Automaton should not be an abstract class, since it hardly makes sense to have an actual machine of unspecified type.initializeForView method, and then adding in a call to requestFocus().
myView.add(this);
this.setEnabled(true);
this.setEditable(true);
this.setCaretColor(null);
this.requestFocus();
Today, I worked on figuring out exactly how the components of the GUI are tied together and how the machine building tools (GUI tools) are implemented.
I started today where I ended yesterday - trying to get scrolling working for scaling. With a couple of print statements, I realized that the issue is the following: since we're transforming the graphics object itself to scale, the states within the automata itself don't notice any difference. In their coordinate plane, they're still where they were before. Every point in their space has simply been translated to a point further away from the origin by the value of the scale.
I am attempting to replicate the transform in the Drawer, so it can compute correctly, but this is causing very strange bugs.
Had a meeting today with Professor Rodger, then went to lunch. We talked about the scroll issues, and implementing undo by means of a snapshot (similar to a file write of the current editpane status except this would be in the memory). We would also feature a limited (finite) multiple undo using a structure that would represent a cross between a stack and a queue. We would push actions onto it while discarding the bottom (after the limit was reached), and pop things off the top when performing an undo. I was also reminded that I had forgotten to get rid of the annoying need too click earlier - the fix for that is actually in a previous journal entry. Finally, we discussed CVS, and how it would easier if there was a jar file so Professor Rodger wouldn't have to launch Eclipse to check our progress every time. I plan to make a script to auto-jar the repository soon.
It turns out that our friend Mr. Finley had already made a script for JARing. I combined it with cvs checkout, changed it to include java files as well, and put it into a crontab, executed every night at 8:00 PM. In the process, I learned that crontab is machine-specific. The crontab that I installed runs on linux21.cs.duke.edu.
So, I have the scroll-bars working - kind-of. After you zoom, if you want scroll bars, you have to twitch one of the states and the zoombars will be activated. Alternatively, if you click on the size-slider instead of dragging it that seems to work too. I believe it's a timing issue with the signals which I am still trying to resolve.
Final Comment: Working zoom with scrolling.
Since I playing with the GUI yesterday anyways, I decided to fix the nagging extra click thing first today. I'm looking at the automata.Note which I saw earlier, as well as the Transition Creator and TransitionTool classes. It seems that the Transition abstraction is separate from its GUI counterpart. I am seeking the GUI counterpart.
The insertion must happen in the MouseReleased function of TransitionTool.
Who is listening for the event that a transition is clicked on and then activates it on it? Who gets the focus?
While trying to work out things, I put in printlines in a lot of places. That's when it occured to me that a Debug class would be nice so it'd be easy to get rid those statements.
I am still trying to find the MouseListener for starting editing. I've found one for stopping editing, hidden in the TableTransitionCreator class. Incidentally, it does not seem to make much sense for classes handling mouse-based editing to extend a TableTransitionCreator.
The label on transitions is a table????????
The actual transition creation code is in TableTransitionCreator...absolutely lovely...okay, I quit for the day...
Since I was having little success trying to brute-force the click thing last Friday, I decided to start by fixing the click for the Note, which I had already discovered earlier. The Note is now immediately highlighted and ready to be typed into on creation.
I think I'm beginning to realize why the point-click is hard on transitions - the issue is that it's a JTable, with potentially multiple fields so requesting focus on it is unexpected.
Looking up JTable API, there is a fun little editor called editCellAt(row, column). It seemed magical, but it worked, even as requesting focus does not. Now I need to test it on all the types of machines, to make it doesn't do anything redundant or stupid because an input was already prompted. As I was testing on the Turing machine, I noticed that it allowed more than one character on the input string in a transition, even though it subsequently gave an error to say that the format was bad.
There appears to be an issue with tabbing in multi-column cases though. After the first cell is edited, a tab does not table you to the next cell as it should. I found the solution by Googling for 'JTable set cell focus' as opposed to generic searches focus-grabbing in Java. Now it has the desired effect, at least in Windows. This forum post was immensely helpful.
Now, the click for both the note and the transition editor are fixed, at least on Windows. I'm going to test it on the other two platforms now. In that process, I found we had a CVS issue where the command line CVS did not recognize a new directory had been added to the repository.
I got the answer from this thread.
I also disocvered I can no longer log into CS machines through a GUI. I'm currently debugging that since the lab staff gave me instructions.
In the process, I found that the issue was with the fact that I was using an ugly hack in my login script in order to use bash. The sysadmin fixed my actual login shell, I got rid of the hack, and it worked.
In the afternoon, I tested JFLAP on the linux machine and attempted to test on Liz's apple. However, Liz's apple gave me a BadClassVersion error. Her version was 1.5.016. I believe it's just that I'm not compiling with a backwards-compatible flag, but I'm making note of it, in case we get version issues in the future. JFLAP has now been (briefly) tested on a Mac, since Liz upgraded to Java 6. My next project will be refactoring a little bit (based on prior notes), and then the undo. I would do the undo first, but I believe adding more features will complicate even minor refactoring.
I'm going to start with simple things, like removing public constructors that should never have been used, and never were used. Here are a list of refactorings:
Today, I started by briefly checking the zoom against the save. It seems that the behavior is as I expected. When you save, the automata, but not its zoom level, is preserved.
Then, I decided it was time to figure out how to implement Undo in the framework.
I copied the Delete Tool to make an Undo Tool, and added it to the DefaultTool, which does not seem to be the same as the one for Mealy, but is shared by Finite Automata, Pushdown Automata and a Turing machine.
As I'm working out how to detect changes, using printlns in the setDirty method of gui.environment.Environemnt, I notice one problem where a simple transition drag and drop registers as multiple events rather than a single event. For my undo, I don't want every point in a drag to count as a separate action - the action should only register when the drop is released. I'm currently tracing through the call hierarchies to figure out who calls these events, and how I can safely make it do what I like. The call hierarchy tree is quite dense, as expected, since many changes will dirty the Environment. Unfortunately, the issue seems to be that the dirty is invoked on MouseDragged, rather than MouseReleased.
Before I make any changes, I have to first figure out how many times the call happens in each of the calls that trigger the dirtying of the page.
These calls go through the setPoint method of automata.State (this is just one caller) : (use hierarchy)
I will resume this tomorrow.
I'm still working on Undo. Today, I continued to explore where the currently present save-based dirty bit is set, to figure out whether it might be easier to set my own flags or modify the current flag. I found that the Automatic Graph Layout causes as many calls to setting dirty as there are nodes, rather than simply 1 each time.
It seems that my dirty bit will be different from the current one used, since its less scope, so it will be easier for me to cover all my bases.
I experimented with altering the four places where setPoint() is called on State to be MouseReleased instead of MouseDragged, to simply things, but that had other issues because the notification of dirty as it current is, is intimately tied with the actual GUI.
How can we tell when an "action" is completed? I can employ the minimalist approach, whereby I let each action I care about inform me when it's done, but there are complications with other kinds of machines - such as state creation in a Mealy or Moore machine, which come in multiple parts.
I'm also thinking about where the state for the undo ought to be saved.
I decided to look at the source code for other applications that implement Undo. I'm looking at Vim source code now. Okay, I give up on that, but I have another idea. Let "action-starter" method first do a method call into the save-storage class that will say "I'm starting an action." The insight here is that it is the beginning and not the end of actions that matters. The action will block on that method call until the save is completed. Now I just need to exhaustively list these "action-starter" methods. Also, the method has to be smart enough to see if the current state is different from the previous state - that is, if I click on a state and do not drag it, that should not be stuck on top of the Undo buffer. Similarly, if I start to create a transition and then do not complete it, then the state of the automaton should not have changed. I'm thinking something like a Hash could help with this.
Today, I decided to first remove the static nature of the UndoKeeper, since we want one per AutomatonEnvironment, ideally. Therefore, I've made it an instance variable in the AutomatonEnvironment.
In order to modify as little existing code as possible, I'm not going to modify the constructor parameters for AutomatonEnvironment, instead simply making a set method to initialize the UndoKeeper.
Now, I'm trying to implement some intelligence in the undo, so that it does not blindly store state even if the state is unchanged. Then I'll implement the other (non-delete) undos.
Unfortunately, nobody has yet written an equals() method for Automaton, despite the fact that there is a clone method, so it looks like that will be my nontrivial task.
Today, I started by putting in the save-state command for actions other than delete. There were some slight issues with the timing of the calls to repaint, or at least I initially thought so. However, it turned out to be an issue with the way I was transforming the Automaton, since the garbage collector came around after I had hoped it would. Manually removing transitions on the clear, rather than waiting for the garbage collector solved the problem. I am also adding the UndoTool to other toolboxes, just for testing. After I am satisfied that the functionality is working, I can fix the trigger so that one does not have to click the Undo tool and then click wildly in the area.
Also, MooreStateTool works better without a trigger, because the second action doesn't need to be saved anyways.
I was going to spend more time testing today, but Jonathan was getting frustrated with the CurvedArrow drawing, so I helped him work on that.
Going back to Undo, I need to benchmark how bad storing an infinite number of undos can get, so I'm looking at JConsole to monitor it. This benchmarking will be systematic, as soon as I get the system up for it.
Apparently, JConsole is fairly easy to use; I followed the instructions here.
Now, I'm exploring automated testing, using the Java Robot class.
The Robot class allows Mouse movement as well as keyboard input. I think that is sufficient to test JFLAP, most motions involve click or click and drag. I can write a tester (for each part) that takes in a list of coordinates, creates states at those points, adds transitions between specified coordinates, performs deletions, and invokes Undo.
Automated testing will allow for a great number of repetitions with a single script, thereby allowing both improved benchmarking and less effort.
At the end of the day I have a prototype tester for the Finite Automata, but it does not yet take input from a file. Currently, the actions are simply hardcoded, to see if the Robot can do what I ask.
I have an idea for a file format of test files (at the basic level) as well. Each line of input will start with a letter indicating the type of action, such as S for State, T for Transition, U for Undo, M for move, followed by a well-specified list of parameters.
Today, I worked on my automated Robot-class based tester. I worked on resolving an issue with transition characters, since there can be more than one, and also, certain character don't easily convert between ascii and keycodes. For now, the testing is limited to alphanumeric characters.
I did find one bug in the Undo, which is if you create self transitions the undo acts as though they aren't a separate action, but are part of the previous action. I am working on resolving it. The issue was that the specialHash uses xor, which is great unless from and to are the same state, in which case it always returns 0, and thereby contributes nothing to the specialHash of the Automaton.
I believe the testing mechanism is working now. Now I just have to create actual tests, other than randomly generated states and transitions. In the random test I saw one case where the undo did an extra step.
I discovered today that Java String.split() does not create empty strings when splitting an expressiong like ",,,,,," on commas. Instead, the split method simply returns an array with no elements in it.
This caused a miner bug in my testing, so I'm fixing that by inserting spaces between adjacent commas. I spent the rest of the day working on the testing parsers for the other types of machines today. While I was working on Turing machine tester, I also discovered that the Transition Tool and the Block Transition Tool had the same hotkey, which causes the hotkey for the simple Transition Tool to break. I fixed this by making the Block Transition Tool take an uppercase T rather than a lowercase one.
One feature I feel would be useful and fairly trivial to add would be group-select-delete. If I see you before you see this entry, I will ask you about it. I think it's a significant limitation that one can only delete one thing at a time. In almost every graphical editor, there is a way to select multiple objects and delete them simultaneously.
Towards end of day, Jon found a bug when converting to DFA caused by the Undo implementation. I'm fixing that.
Jon then found 3 more errors that I didn't find when Iw as testing. mostly related to menu options that I failed to test. The issue was that my implementation of Undo reached into parts of JFLAP that inherited from those I directly modified. I inserted a check against null to restrain the effect to the main editor windows, where it was most useful and logical.
I started by reading over some bug reports, to get a better idea of where the bugs tend to crop up before I continue writing tests.
One error I saw a couple of times was heap space issues, which I believe will only grow worse with Undo. I am looking at how that may be increased without requiring the user to use the shell.
First, though, I have to try to reproduce it. I reproduced error11, and then tried to run it with -Xmx256mb. This caused it to last a little bit longer on StepWithClosure, but two more runs and it was also toast. The issue is that the number of valid configurations for that example increases by a factor of 4 at every step, and such exponential increase easily overwhelms whatever amount of memory we try to allocate for it.
I'm thinking we will simply have to alter the functions that have this possibility to quit gracefully after a certain number of configurations has been exceeded and alert the user that such numbers are not within the scope of JFLAP. I am currently looking at the other memory errors to see if they are similar.
Error 26 seems to be a similar issue. I think it might be useful to compute and inform them of the number of configurations they're trying to generate.
I'm currently looking at Error12, since it looks like it is either solveable by increasing memory allocation, or it's a literal bug in our code.
Error 13 looks like 26, but without more information, I can't be sure.
Error 55 should be solveable by increasing memory allocation, since that's a simply string concatenation.
Should we put a strict cap on exponential configurations, or shoudl we give the user the choice to continue until the actual OutofMemory error occurs? My opinion is that we should put a strict cap, since JFLAP was never meant to be an industrial tool, but rather a teaching tool. Jonathan thinks that we should give the user the choice. That is, when a certain number of configurations is attempted, we give the user a dialog box warning them that they might run out of memory, and ask them if they want to continue anways.
I'm looking at DFA errors now. I reproduced Error 08. I figured out why there is no exception thrown on the second attempt (one puts thhe newly created state into the map right after the exception is thrown), but I'm trying to figure out why the map would have an extra entry for that particular label the first time around.
After some discussion with Jon, and cross-checking, we realized that the NFA-to-DFA conversion algorithm might be flawed. When we use the bug reporter's strategy of trying a second time, and putting in 0,0 after the exception is thrown, and hit complete, JFLAP tries to finish the DFA, but it cannot pass its own checker; "Done" button says it is incomplete, and manual analysis reveals the same.
I spent the rest of the day trying to understand how the ConversionController works, and how it utilizes the helper class NFAToDFA.
At the end of the day, I changed the containSameStates method in NFAtoDFA to fix the bug, but I'm not sure if that was the only bug, so I will look again tomorrow.
I started today by looking over the Error-contain code from yesterday, to better understand it and look for more errors. I did not see anything else particularly interesting.
I'm also sending some emails out to ask about certain errors.
Looking over the JMultiLineToolTip errors, I notice that 8/9 are on OS X, and one is on Windows Vista, which may explain why we've been having problems reproducing it. I'm looking at the class now for implementation-specific bugs. It looks like the issue is that getPreferredSize is not necessarily called before paint is called the first time. I put a check in the paint method so that it will not try anything if the JTextArea is null. I believe that should be the last of the NullPointerExceptions in the GUI directory.
I sent out two more emails asking about the ConverttoMinimalDFA bug, although it unlikely that people will still remember, given the time distance.
Looking at some of the grammar errors and trying to reproduce the IllegalArgumentException, I accidentally reproduced error04, so I'm currently investigating that.
What happens after the first error? Are we not cleaning up properly, causing the NullPointer to also be thrown? Also looking down the call chain where we eventually get the Grammar object from.
gui.grammar.GrammarTable seems to be throwing two Exceptions, both of which appear in the error reports for grammars. However, neither was the culprit for error04. I am temporarily adding in a test against null for GrammarTypeTestAction, and am continuing to try to understand the relationship between the first JFLAP-type error message and the Exception.
The JFLAP error (saying that the first production must be restricted, rather than unrestricted) which precedes the NullPointer originates as an exception in grammar/UnrestrictedGrammar.java, in the addProduction method. It is then caught by gui/grammar/GrammarTable.java, and transformed into a message dialog informing the user. However, the try/catch block which transforms the Exception is in the getGrammar method of GrammarTable, and the method returns null on the exception, thereby triggering the NullPointer in error04.
There were three error reports that referred to this error, so I moved them into the Fixed category.
Now looking at Error23. I'm going to read a bit more about grammars, since I need a better idea of how the UserControlParse is supposed to behave.
I spent becoming more familiar with JFLAP's handling of grammars, so I would be able to better address the grammar-related bugs. Switched to Redo after meeting with Professor Rodger.
There is one caveat that I have to decide with Redo. What should I do if someone does something, hits Undo, and then does something else? I think the easiest thing would be to discard the Redo deque. So, I have redo working, with the caveat that it clears redo memory whenever a separate action follows an undo, but it still needs to be heavily tested.
While testing, I noticed another issue that might be different between linux and windows, which is primarily relevant for automated testing. In Windows, when I right-click with the selector tool on a state, it does not automatically highlight the first element, but in linux it does. This matters because part of the automated testing is to set final and initial. On Windows, it takes two Down keypresses to get to the Set Initial state menu item, but in Linux it takes only one. Mac behaves like linux in this respect. I'm looking at whether there might be an easy way to make it consistent across all the platforms. So it looks like I can fix my testing tools by moving to the right two pixels and then moving to the left again...okay, that didn't work, because apparently Java (in *nix) does not respond to the down key when the mouse is out of focus. I tried playing with LookAndFeel, but that does not seem to do the trick.
In the end, I decided to try fixing Windows to select the first item, but that did not work out either. For some reason, the JMenuBar is resistant to such calls asSelected, or clearSelection. I will investigate this further on Monday.
I spent the morning helping people get online, primarily NetReg, and releasing/renewing IP Address. I also helped some people get Alice working by reducing the amount of memory requested for the heap. Since Wanda mentioned that people should write down their system stats when Alice was failing, I spent about 20 min of downtime in the afternoon writing up a small Java program to dump system properties into a file. This jar is available here.
I helped with the workshop today. Only really interesting incident was this guy where netbeans import would not work. After about ten minutes, I tested a different project import and realized that he had something in his Alice world that wouldn't translate. We fixed that by removing the offending feature.
I attended the last bit of Rachel Brady's talk, and then helped direct people to Teer. When I returned to the office, I continued where I left off Friday, trying to make my testing framework consistent across all three platforms.
I actually spent a good deal of the afternoon setting up command line CVS over SSH, before I started working on Windows again, because I feel a lot more productive that way.
At the end of the day, I did get the Tester working for FA's. I will do the others tomorrow and work on an error that Jon found with Undo/Redo.
I had intended to attend the conference, but I ended up helping with it as well, from Apple machine setup to helping some people with Java API. I actually learned a good amount of the Graphicsc2D API during the lecture though. "Baby engineers...we give them engineering problems but they don't recognize them as engineering problems because they haven't had enough enough engineering experience." Data Structures in Media Computation...they'll take Media Computation but not Computer science... "Special Mexican popsicle that's only made in Durham." Processing Digital Sounds: Media tools make it easy to record and play sounds (using squeak VM) - just type squeak with any squeak image as an argument.
Linux seems to have a funny graphics issue with Mealy Machines. The letters in transitions are all jumbled together.
Clone does not actually copy notes, it would seem.
First, the cloned note does not have initializeForView() called on it. This becomes a problem if we want the cloned note to actually be displayable - the view thing must be restored.
Second, who calls updateView on the note?
Also, what does the delete tool do that I am not doing when I clear the automaton.
Apparently, the DeleteTool's mouseclicked function never gets invoked when deleting a note. Somebody else swallowed the event.
So, there's an interesting hack where the Note handles its own deletion, using its mouseClicked function, and checking whether the delete tool is selected.
in PDA, if I make two states, make a note, make a transition, hit undo, delete the note, and then hit undo, it gets screwed up.
I repaired this by finding where the note was not saving status.
I did a serious benchmark, with 2000 states created, and that blew up in my face, so I will have to limit the undos. Here are some screenshots of memory usage:
The blowup came up in this very interesting type of OutOfMemory error:
Exception in thread "RMI TCP Connection(idle)" java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.lang.AbstractStringBuilder.(AbstractStringBuilder.java:62)
at java.lang.StringBuilder.(StringBuilder.java:85)
at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.run(TCPTransport.java:664)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1110)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:603)
at java.lang.Thread.run(Thread.java:636)
Exception in thread "Image Fetcher 0" java.lang.OutOfMemoryError: GC overhead limit exceeded
at sun.awt.image.PNGImageDecoder.(PNGImageDecoder.java:640)
at sun.awt.image.InputStreamImageSource.getDecoder(InputStreamImageSource.java:242)
at sun.awt.image.ByteArrayImageSource.getDecoder(ByteArrayImageSource.java:59)
at sun.awt.image.InputStreamImageSource.doFetch(InputStreamImageSource.java:258)
at sun.awt.image.ImageFetcher.fetchloop(ImageFetcher.java:189)
at sun.awt.image.ImageFetcher.run(ImageFetcher.java:153)
Jun 22, 2009 3:59:14 PM sun.awt.X11.XToolkit processException
WARNING: Exception on Toolkit thread
java.lang.OutOfMemoryError: GC overhead limit exceeded
at sun.awt.X11.XFocusChangeEvent.getFieldsAsString(XFocusChangeEvent.java:67)
at sun.awt.X11.XWrapperBase.toString(XWrapperBase.java:37)
at sun.awt.X11.XFocusChangeEvent.toString(XFocusChangeEvent.java:8)
at java.lang.String.valueOf(String.java:2838)
at java.lang.StringBuilder.append(StringBuilder.java:132)
at sun.awt.X11.XDecoratedPeer.handleFocusEvent(XDecoratedPeer.java:244)
at sun.awt.X11.XFocusProxyWindow.handleFocusEvent(XFocusProxyWindow.java:79)
at sun.awt.X11.XFocusProxyWindow.dispatchEvent(XFocusProxyWindow.java:72)
at sun.awt.X11.XBaseWindow.dispatchToWindow(XBaseWindow.java:1056)
at sun.awt.X11.XToolkit.dispatchEvent(XToolkit.java:488)
at sun.awt.X11.XToolkit.run(XToolkit.java:583)
at sun.awt.X11.XToolkit.run(XToolkit.java:518)
at java.lang.Thread.run(Thread.java:636)
I did some reading on this, and apparently this only comes up if the GC uses more than 98% of CPU time and less than 2% of the heap is recovered.
I ran the same benchmark as yesterday, this time on my Windows machine which had 1 GB of RAM. and it crashed at about six hundred actions, with an OutOfMemory error which mentioned that it did not have enough memory to display the AWT error message.
I think in the light of this, I will have to give the user the option to change the number of Undos stored, since it varies with the system to a significant degree.
Since I wanted to also get some sense of how much Undo slows JFLAP down, I tried against the source we started with, and it seems that, with 1000 states in play, they're about equally sluggish. That actually makes me curious now, about what part of JFLAP is causing the slowness, and whether there might be a way to optimize. If it's the graphics drawing, we could detect for overlap, and only draw the topmost state.
I looked at the drawing code, which is simply loops through all the states and calls draw on each. I think even a naive optimization would be useful, at least to reduce the drawing overhead for testing. If I went through the list of states and drew only those that were not utterly covered by others, I think it will increase the speed a great deal.
I'm currently adding an option for number of Undos to the file menu.
Finishing with that, I decided to start looking at SVG, since Jon had tried it earlier and had been unsuccessful.
Vector graphics export is now working, but with limitations of deployability. I am looking at java Class Loaders to try to circumvent those limitations.
The issue is that the library jars cannot go inside the main jar and still be found by Java's class loader, and I'd rather not force people to download a zip and unzip it before they can use it, although that is the other option.
I am not going to commit the libraries and Manifest files until I resolve this issue.
Make sure that all the licensing issues are resolved before you leave - the batik library is released under the Apache License 2.
I finished getting the batik library code into the repository, so our vector graphics now work. However, while I was trying to do a comparison with the raster graphics, I noticed that Jon's export image does not work consistently on linux. I fixed it, as well as adding a couple of file filters, to make the interface more intuitive. I also refactored that part of the package, and added a check so that we wouldn't inadvertently overwrite files. Finally, I made it so that the extension is appended only if the extension is not already acceptable.
There was a slight problem with this, in that I couldn't get the save dialog to stay open. I investigated how JFLAP handles the overwrite detection in the writing of JFLAP fields, and I saw a similar hack, with the Save Dialog box dissappearing, so I'm going to keep what I have.
I plan to start looking at Building Blocks tomorrow, to see what is there, how hard it is to generate bugs, and how it can be improved.
Looking over Building Blocks tutorial. The screenshot for the variable assignment section seems to be missing entirely.
Notes go crazy under zoomed conditions, so I'm looking at that. Trying to figure out where the Note is added to the view, since I see places where it is added and removed from the Automaton, and removed from view, but never where it is added to the view.
It would seem that the Note uses the transform to map itself, and that is partially what is causing the problem. Rather than transforming its own graphics object to match the transform on the graphics object of its parent, it attempts to manually figure out where the point is, and draw as though it were painting on the user's canvas. I believe the solution to this is to disable the manual point-finding in the Note class and then manipulate its graphics object to use the same transform as the rest of the Automaton is using.
I also attended Richard Lucic's brief talk on the VCL, and gave DIVE tours today.
Spent an hour this morning failing at trying to help Liz print. In the end, KPDF fixed it.
I worked a bit more on the zooming notes, but Jonathan fixed that using something that I don't quite understand.
Also did the Alice 3 Demo today. The working install is on machine 24.
I went back to looking at building blocks code.
In the blocks, each one knows its parent, but it does not know its children. I tried to understand how the building blocks work by tracing the program using the Sun's Java Debugger, jdb, but I found it extremely unuseable, given the fact that there is no easy way to repeat last command, and all commands have to be fully typed out. Even though it has a very small number of commands compared to GDB, so there is much less room for ambiguity, I have to type out the full word "next" and the full word "step" every time I want to do one of these. Also, apparently there is no way to step [count] number of times.
I started this morning looking over the building blocks code, thinking about what I might add to it. Then, I tried to search for Turing's World software, but all the links to the actual site seemed to be broken. I also found a few other softwares similar to JFLAP, mostly listed here. The most similar seems to be something called the Java Computability Toolkit. I spent some time reading documentation for these, to see what I might add to JFLAP.
I also did some reading on maintaining and contributing to an Open Source project, so that I might have a better idea of how to make JFLAP not fail if and when we take it open source.
Some of the links I looked at for that:
Spent the day playing with Turing's World, following along with the book. Trying to find a way to contact Jason Strober for Turing's World source code.
Things I found that would be useful in JFLAP in general:
Spent the day playing with Turing's World, following along with the book. Trying to find a way to contact Jason Strober for Turing's World source code.
Things I found that would be useful in JFLAP in general:
In Turing's World, you can turn a machine into a submachine, which is convenient, but you cannot import from and export to files with submachines. Spending some time weeding out errors in our building blocks, and then seeing about copy & paste features. Line 151 of TMSimulator has a fixed-size array. I'm utterly confused. Java Generics style would force the guy to say what "parentBlocks" actually IS, instead of a TODO with question marks. Is there only one final state in a block? See finalStateInBlock in State.java. Is it mutually exclusive? Ah, okay, so that boolean keeps track of whether there is a final state at all in the block. OpenAction caches the last file opened statically, which allows BuildingBlockCreator to call it and then query it later. That seems a bit of an odd hack. static void openFile uses an OpenOrRead flag that is specific to Building Blocks. ----- Oh, I called Dr. David Barker-Plummer at Stanford today. It seems that they discontinued development on Turing's World because JFLAP did the same thing. ---- makeListFromArray in Automaton.java seems to be easier to implement if we just use Arrays.asList(); //I might correct that. It appears that, in our implementation, each Autamon keeps track of the individual states in its blocks, but NOT of the states in their sub-blocks, if they have any. It would be good to test the behavior of step-by-building-block under the situation of nested building blocks. - this is from looking at the method putBlockContentsInAutomaton. - I think this can be simplified if parents kept track of their children, instead of the other way around. In Turing's World, they will step at arbitrary granularity if you step by state, although they do not give the option to do not do that while in step mode. Also gave DIVE tours today. I talked to the Vis group person today, and she said it was okay to show different worlds. So next week, I might show a greater variety of worlds. Some worlds we will only experience a little bit, but I still feel that we can do better than showing Tartarus all the time. I got JFLAP to crash with EmptyStackException by trying to run a Step while editing a block. Also noticed a more subtle bug, where if you edit a block that is an initial state for the bigger Turing machine, and then return to the main pane, the arrow is not redrawn until one moves that state again. - Correction: You just have to hit Step, and try to step through a turing machine in non-building-block mode, and it will crash. - Correction: Building blocks are simply broken: When I step by Building Block is terminates prematurally on the same thing that was in the Building Block. (when that was focused) Fast Run does not show the final state of the tape, only reject or accept? Also, can we disable the accept/reject part of Turing? Does JFLAP only ask about save with settings other than Initial/Final? As in, I set all states to Final, and closed without it asking me to save. SO, it seems that we cannot do what Turing's world does: Run a Turing machine straight through, and see the final state of the tape at the time of halting. Or at least I haven't found a way to do that. Also, when we open files, we should be able to use the file name without the jff extension. JFLAP should be intelligent and look for both names. This way, it will parallel when we save, where we don't have to explicitly type jff. Cannot find other accepting configurations. Dual settings - definition of Turing Machine. Separate definition of Turing Machine - another option - but keep the old way for consistency (important). Only step or change rather than allow both step and change - use algorithm to convert between definitions. Fix CVS issue...
So, last night, I realized by Thomas Finley's python script is a bad idea; it hides the real error by swallowing it, and makes it look like the jar works, even though it obviously does not. I replaced the use of the script with a simple bash command in the Makefile, using a file as a buffer to get around the limitation on number of command line arguments.
Today, I started by looking at the save bug, where if the Automata was the last Window open, and it was closed, it would not register that it needed to save from setting of final state. It seems to be an issue with Undo as well, since the setting of initial and final does not invoke a call to save the state. Had to modify the hashCode() in automaton to account for final and initial states.
I fixed Undo by editing the hashing function and also adding in a method call where initial and final is set. I fixed the save bug by adding a distributeStateChangeEvent into Automaton.java where initial and final are set and cleared. While I was fixing the save bug, I also noticed that the save bug includes notes. When we have a Note that is added or deleted, JFLAP is also not aware of it when it comes time to close. For the note, I've added AutomataNoteEvent and AutomataNoteListener.
It's actually somewhat tedious to get Note Changes to register, because that has to be done from within the Note (for both Undo and Save-Check), since it handles events on itself.
Also, Undo needed to detect changes in Note contents.
I wanted to start looking at building blocks, but then Jonathan had a CVS issue where eclipse would delete library class files for no reason. I'm looking into that now.
So, Turing machines parse their input as a STRING ARRAY, while regular machines parse their inputs as a STRING.
BlockMap in an automaton is a mapping from Strings (internal name) to Automaton (the ones within blocks). The need for this structure seems to stink of bad design. I think it would be much cleaner if states simply stored the "myInnerMachine" automaton internally. Currently, the technique to finding the deepest layer is to query each automaton's blockMap until we get to the innermost (this is for getting initial configuration).
Just had a thought: If turing machine does not have a final state, then it will reject everything, and the only way to get it to run at all is by stepping one step at a time. I feel like that's not giving the user a lot of options.
Looking at calls to cloning a stack in Line 99 of TMConfiguration. Writing a short program to see if the clone is shallow or deep. It is shallow.
JFLAP does not complain when there is no final state for Finite Automata, PushDown Automata, or Turing, but yet it will never accept if there is no final state.
In TMSimulator.java, Lines 163 - 166 seem like a ridiculous waste of CPU. Also, that while loop seems to be modifying the actual automaton stack and block stacks of the configuration that is passed in, shearing away the top of both stacks until they have a single element left, whenever the currentState is NOT the final state in a building block.
I met with Professor Rodger at the end of the day to talk about the poor design of the Building Blocks code and we decided that I should look through more definitions of Turing machines in different books before deciding on a new design, running it by her, and implementing it.
I spent some time today reading Turing's Paper, discussing Turing machines with Professor Rodger, and reading some varying definitions of Turing machines. I will reiterate here that I want to terminate on the 17th, so I will need to move quickly to do everything with Turing machines that I think would benefit JFLAP. Since many facilities close early today, I am leaving at 3. Since I did not clock time for today, there is no need to correct any time cards.
I read through the Turing machine descriptions and examples in two more books today, and made notes on the formalization of Turing machines.
I finished reading through Turing machine definitions and making notes on them. I'm currently listing a set of features my new design should have. One thing that might be an issue is conversion to Unrestricted Grammar. I think I can solve that by doing a complexity test before allowing the user to perform conversion. For example, simply disallow it for machines with Building Blocks.
I spent the morning working on the redesign of JFLAP Turing Machines, and consoulted Professor Rodger about potential changes that I think would benefit JFLAP, keeping in mind the primary objective: Fixing building blocks and making it easier to augment or restrict the definition of a Turing machine for the user. One of the more difficult issues to think about was how to make the changes as transparent as possible to the rest of JFLAP. From this challenge, I decided to try to separate as much as I could the Turing-machine specific from the non-Turing machine specific. Unforunately, I have to compromise a little bit because I do not want to rewrite the code that calls Automaton-level and Automaton-Simulator level methods. Therefore, for the deterministic Turing machine, we will be passing around one-element Collections and Arrays. The determinism will be enforced, however, and to simplify internal programming, the internal data structures of the parent will be ignored in the TMSimulator. (Spent about 40 minutes with unsuccessful, and also incorrectly timed DIVE tours. We will do them tomorrow.) I have started working on proposed changes. Classes Modified or Examined:
Working on continuation of yesterday. See the list from yesterday's notes, which I've extended for today.
Started looking at some of bugs that Professor Rodger found, trying to get the old stuff working again (in building blocks). Trying to understand why duplicate string fails prematurely, by tracing my own logic. It would appear that saving (or at least loading old files is not preserving the parent relationship, which makes sense, since I don't think I coded that in.I'm looking at AutomatonTransducer again. Trying to get duplicateString to run - The issue with not running Duplicate String is a combination of two things. First, the parent of the inner Automaton was not being set properly, which I fixed after some time using assertions. The second thing is that it used features of JFLAP which I had temporarily disabled. - I fixed an edit issue while I was looking at this as well. - I'm looking at Save bug, and then going to add back in the features that I took out, to get duplicateString to work. - Apparently Null is a valid key for a HashMap. - Fixed the save bug, am now looking at adding back features (Multiple-tape, variable assignment and whatnot - The key to make this work correctly is to separate the reading phase from the acting phase. First, we determine whether we match, and THEN we figure out what to do.) - I think I'm going to try to make the TMSimulator flag the TMConfiguration as halted or not halted, and this will make the filter trivial, although it will be one step later, potentially. hmmm...when we say NOT, do we mean NOT, and also not anything that is already matched? if so, we could get more complicated. - in other words, if my alphabet (which is currently ill-defined), is {a, b c}, and I have two transitions out of my state, one of which is Not b, and the other one which is "a", and I get an 'a' under the tape head, does this become nondeterministic, or do I choose a, because it has higher priority than "Not B?" - ask Prof. Rodger tomorrow.
There is no reason for variables to be tape-specific, is there? Oh, so apparently variables did not work on multi-tape machines in the old JFLAP. For the sake of time, I will have the same restriction. For the sake of determinism, I will further remove the NOT from multitape machines. Also, the old version does not correctly handle a combination of NOT and variable assignment, when the NOT is not the first character. I will try to do better. Re-instill replace-symbol as well. After talking with Professor Rodger, I am now going to change the following two things: 1. Enforce the Alphabet-only rule on the left side of the right curly brace. (this rule is enforced at run-time, when they attempt to step and one of the things on the left is a variable) 2. Forbid the use of the ! operator alongside an assignment (this will be done at build-time ) - this is just a check to make sure both characters are not present in the read-string part of the table. - assert at run-time 3. Forbid the use of the ! operator in Multi-tape Turing machines. ~ is still allowed universally though. 4. Forbid the use of regex in Turing machine. How does JFLAP show error messages? Ask Jonathan to split transitions in getTransition (so that the regex is transparent to the outside), if we want regex in Turing Machine, but not sure if that will happen. Might change varToChar to a Character, Character map so I don't have to keep appending null string. stepByBuildingBlock needs to be put back in as well.
I read through your email, and I will document changes a little bit later today. I'm looking over the list of unimplemented features that I'd hoped to implement, and hacking away at some more of those.
Tasks for today: