This discussion is archived
13 Replies Latest reply: Mar 8, 2012 6:14 AM by Kleopatra RSS

Handle long-running EDT tasks (f.i. TreeModel searching)

Kleopatra Journeyer
Currently Being Moderated
Note: this is a cross-post from SO
http://stackoverflow.com/questions/9378232/handle-long-running-edt-tasks-f-i-treemodel-searching

copied below, input highly appreciated :-)

Cheers
Jeanette

Trigger is a recently re-detected SwingX issue (https://java.net/jira/browse/SWINGX-1233): support deep - that is under collapsed nodes as opposed to visible nodes only, which is the current behaviour - node searching.

"Nichts leichter als das" with all my current exposure to SwingWorker: walk the TreeModel in the background thread and update the ui in process, like shown in a crude snippet below. Fest's EDT checker is happy enough, but then it only checks on repaint (which is nicely happening on the EDT here)

Only ... strictly speaking, that background thread must be the EDT as it is accessing (by reading) the model. So, the questions are:

- how to implement the search thread-correctly?
- or can we live with that risk (heavily documented, of course)

One possibility for a special case solution would be to have a second (cloned or otherwise "same"-made) model for searching and then find the corresponding matches in the "real" model. That doesn't play overly nicely with a general searching support, as that can't know anything about any particular model, that is can't create a clone even if it wanted. Plus it would have to apply all the view sorting/filtering (in future) ...
// a crude worker (match hard-coded and directly coupled to the ui)
public static class SearchWorker extends SwingWorker<Void, File> {
    
    private Enumeration enumer;
    private JXList list;
    private JXTree tree;

    public SearchWorker(Enumeration enumer, JXList list, JXTree tree) {
        this.enumer = enumer;
        this.list = list;
        this.tree = tree;
    }

    @Override
    protected Void doInBackground() throws Exception {
        int count = 0;
        while (enumer.hasMoreElements()) {
            count++;
            File file = (File) enumer.nextElement();
            if (match(file)) {
                publish(file);
            }
            if (count > 100){
                count = 0;
                Thread.sleep(50);
            }    
        }
        return null;
    }

    
    @Override
    protected void process(List<File> chunks) {
        for (File file : chunks) {
            ((DefaultListModel) list.getModel()).addElement(file);
            TreePath path = createPathToRoot(file);
            tree.addSelectionPath(path);
            tree.scrollPathToVisible(path);
        }
    }

    private TreePath createPathToRoot(File file) {
        boolean result = false;
        List<File> path = new LinkedList<File>();
        while(!result && file != null) {
            result = file.equals(tree.getModel().getRoot());
            path.add(0, file);
            file = file.getParentFile();
        }
        return new TreePath(path.toArray());
    }

    private boolean match(File file) {
        return file.getName().startsWith("c");
    }
    
}

// its usage in terms of SwingX test support
public void interactiveDeepSearch() {
    final FileSystemModel files = new FileSystemModel(new File("."));
    final JXTree tree = new JXTree(files);
    tree.setCellRenderer(new DefaultTreeRenderer(IconValues.FILE_ICON, StringValues.FILE_NAME));
    final JXList list = new JXList(new DefaultListModel());
    list.setCellRenderer(new DefaultListRenderer(StringValues.FILE_NAME));
    list.setVisibleRowCount(20);
    JXFrame frame = wrapWithScrollingInFrame(tree, "search files");
    frame.add(new JScrollPane(list), BorderLayout.SOUTH);
    Action traverse = new AbstractAction("worker") {
        
        @Override
        public void actionPerformed(ActionEvent e) {
            setEnabled(false);
            Enumeration fileEnum = new PreorderModelEnumeration(files);
            SwingWorker worker = new SearchWorker(fileEnum, list, tree);
            PropertyChangeListener l = new PropertyChangeListener() {
                
                @Override
                public void propertyChange(PropertyChangeEvent evt) {
                    if (evt.getNewValue() == SwingWorker.StateValue.DONE) {
                        //T.imeOut("search end ");
                        setEnabled(true);
                        ((SwingWorker) evt.getSource()).removePropertyChangeListener(this);
                    }
                }
            };
            worker.addPropertyChangeListener(l);
            // T.imeOn("starting search ... ");
            worker.execute();
        }

    };
    addAction(frame, traverse);
    show(frame)
 } 
  • 1. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    gimbal2 Guru
    Currently Being Moderated
    So basically your problem is that you have a piece of code that might take a long time to execute but still needs to operate on the EDT, right?

    Idea:

    - do the search in a thread, but don't update immediately. Collect all search results in stead
    - when that is done on the EDT, process the search results
  • 2. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    Kleopatra Journeyer
    Currently Being Moderated
    hmm, not quite (my bad for explaining it not clear enough ;-)

    The long task should operate in the background (on the EDT it would block), but needs to access a property (the model) which legally should be accessed on the EDT only.

    So the update is not the problem, but the access: while doing it - from a background thread (which isn't really allowed) - it might be accessed on the EDT as well.

    One idea on SO was to synchronize both the model and the process on a backing data model. Which isn't really possible in a general way (and in the view itself), IMO.

    Thanks
    Jeanette
  • 3. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    gimbal2 Guru
    Currently Being Moderated
    Pardon me if I continue to fail to understand you :)

    So your issue is with reading from the model of a component (or a tree of components) from a background thread? I could see the problem then; the background thread could be accessing the model while modifications are being made to it by the EDT due to the user doing things and stuff in the GUI. Am I still on the right track?

    If so: my brain hurts :/
  • 4. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    Kleopatra Journeyer
    Currently Being Moderated
    exactly :-)

    My turn to apologize for not being clear enough right at the start - I now see how the subject is misleading, but can't think of a way to improve ... "How to read properties which should be accessed on the EDT from a background thread" might be a better summary

    Thanks
    Jeanette
  • 5. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    gimbal2 Guru
    Currently Being Moderated
    My first brain f@rt (seriously, does that really have to be sensored?) was to keep a shadow administation completely detached from the Swing component model which you can freely scan in your background thread and will update from the component tree upon changes made (through listeners) - that way you can synchronize access to that shadow administration at the lowest level you can manage.
  • 6. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    Kleopatra Journeyer
    Currently Being Moderated
    yeah, that seems (if I understand you correctly) a solution along the lines of what @trashgod suggested over at SO: synchronizing on a backing (the actual treeModel) data model. Which I think isn't completely possible to do in the view (that's where the Searchable which would trigger the worker - is located) for two reasons:

    - the Searchable can't know the backing model
    - the view model might be really a "view" model, that is f.i. filtered/sorted as compared to the backing one

    the former might be changed (maybe, need to think a bit longer), the latter not really

    BTW, my hurting brain sees this as basically similar to a recent (ehem ... some months ago) discussion about doing tree expansion in a way that doesn't block. But maybe not, need to bribe the brain with some coffee :-)

    Thanks
    Jeanette
  • 7. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    800268 Expert
    Currently Being Moderated
    On first thought, it should be fine as long as the TreeModel isn't modified on EDT while the search is running on the background thread (that is, there shouldn't be any thread visibility problems due to synchronizing in SwingWorker).
    However, I've made lazy loading tree models which do exactly that: calling TreeModel#getChildCount(node) triggers a background task which will later fire a node structure changed event (on the EDT) while return "1" and will display a processing node.
    I also have code which automatically removes nodes (for example on node selection to check if a user object has been deleted in the database). Removing is worse since likely to lead to index out of bounds exception in your search thread, while the lazy loading probably leads to nothing found but no exceptions.

    So a background search on any TreeModel is simply not going to work. You could add it but would require a big warning about no modification. It might be possible to provide a synchronized wrapper TreeModel which cancels a search when the underlying TreeModel is about to change (before because that the backing data structure changes before the event is fired) which means all mutating should be done through the synchronized model which you can't do generically since there is no MutableTreeModel interface. Unless you introduce that interface as well :P

    I would suggest the developer implements the background search on the user object structure and than finds/selects/expands the correct node in the UI on the EDT using the user object path (if using DefaultMutableTreeNodes which has a user object).
  • 8. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    Kleopatra Journeyer
    Currently Being Moderated
    lazy loading by busy developers :-)

    Good point - and yet another thingy to think of ... looks like a general solution is harder (as in near-to impossible) than I thought it would be.

    Probably will opt for offereing something like the above and document with heavy warnings as useable-only-in-the-most-simple-contexts (strictly read-only, no lazy loading, no nothing). Plus a way to allow custom plug-in searches (which is already available, implement a custom TreeSearchable ;-)

    Thanks
    Jeanette
  • 9. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    jduprez Pro
    Currently Being Moderated
    Hello,
    Can't do develop an Adapter model that posts all accesses to the underlying model in the EDT(invokeAndWait)?
    e.g.
    public class BackgroundTreeModelAdapter implements TreeModel, TreeModelListener {
        public BackgroundTreeModelAdapter(TreeModel model) {
            this.actualModel = model;
            buildNodemap(); // not shown, should offload the mapping to EDT too
        }
        ...
        public int getChildCount(Object parent) {
            final Object actualParent = nodeMap.get(parent);
            final ResultHolder<Integer> result = new ResultHolder<Integer>();
            Swingutilities.invokeAndWait(new Runnable() {
                public void run() { result.setValue(actualModel.getChildCount(actualParent)); }
            });
            return result.getResult();
        }
    
        ...
        public void treXXXyyyed() {
            buildNodemap();
        }
        ...
    }
    Thinking about it, this approach looks generic indeed - just implement a wrapper for all standard Swing models :o)

    I note that, although it is thread-safe with regards to accessing the EDT, it is not thread-safe with regards to the algorithm that uses it (e.g. if a node is removed in the middle of the traversal algorithm). A "modified" check can be implemented though, and restart, or gracefully fail, the algorithm.

    Best regards,

    J.
  • 10. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    gimbal2 Guru
    Currently Being Moderated
    jduprez wrote:
    A "modified" check can be implemented though, and restart, or gracefully fail, the algorithm.
    Hm, disregarding all epic and difficult solutions involving adapters, external models and synchronization; might this not be the stupid yet effective way to deal with the 'problem'? In the scan thread there will likely be a loop, which could prematurely abort if some "I changed last on this timestamp!" is updated and different from what it was when the thread started?
  • 11. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    jduprez Pro
    Currently Being Moderated
    gimbal2 wrote:
    Hm, disregarding all epic and difficult solutions involving adapters, external models and synchronization; might this not be the stupid yet effective way to deal with the 'problem'? In the scan thread there will likely be a loop, which could prematurely abort if some "I changed last on this timestamp!" is updated and different from what it was when the thread started?
    To ensure visibility of such a control flag across the two threads, synchronization will be involved - and the safest way to do that is that the background thread uses invokeLater or invokeAndWait .
    And even that does not cover all cases: for example, assuming the flag allows the loop to proceed to the next iteration, the concurrent change may become visible anytime during the next iteration, and cause unpredictable havoc.

    Edited by: jduprez on Feb 28, 2012 4:53 PM
  • 12. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    gimbal2 Guru
    Currently Being Moderated
    Whoops, I'm not explaining myself again. One part of my failure is that I didn't clearly indicate that 'external models and synchronization' was one and the same indicating maintaining a shadow copy, I wasn't implying anything about thread synchronization.

    Other than that, I think we have a different view on what an 'iteration' of the background thread actually is. My idea is that the thread loops through the tree on a node by node basis and could be made to prematurely interrupt or even restart in that low level loop as soon as a change is registered. But that is not only guess work, it is also oversimplifying as you'd need to be able to first reliably detect changes to the tree model.
  • 13. Re: Handle long-running EDT tasks (f.i. TreeModel searching)
    Kleopatra Journeyer
    Currently Being Moderated
    At the end of the day, it turned out that I asked the wrong question (or right question in a wrong context ;-): the "problem" arose by an assumed solution, the real task to solve is to support a hierarchical search algorithm (right now the AbstractSearchable is heavily skewed on linear search).

    Once that will solved, the next question might be how much a framework can do to support concrete hierarchical searchables. Given the variety of custom implementations of TreeModels, that's most probably possible only for the most simple.

    Some thoughts that came up in the discussions here and the other forums. In a concrete context, first measure if the traversal is slow: most in-memory models are lightning fast to traverse, nothing needs to be done except using the basic support.

    Only if the traversal is the bottleneck (as f.i. in the FileSystemModel implementations of SwingX) additional work is needed:

    - in a truly immutable and unmodifiable TreeModel we might get away with read-only access in a SwingWorker's background thread
    - the unmodifiable precondition is violated in lazy loading/deleting scenarios
    there might be a natural custom data structure which backs the model, which is effectively kind-of "detached" from the actual model which allows synchronization to that backing model (in both traversal and view model)
    - pass the actual search back to the database
    - use an wrapper on top of a given TreeModel which guarantees to access the underlying model on the EDT
    - "fake" background searching: actually do so in small-enough blocks on the EDT (f.i. in a Timer) so that the user doesn't notice any delay

    Whatever the technical option to a slow search, there's the same usability problem to solve: how to present the delay to the end user? And that's an entirely different story, probably even more context/requirement dependent :-)

    Thanks for all the valuable input!
    Jeanette

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points