Type safety, Java generics and querying

Question

I have an interesting situation and I'm wondering if there is a better way to do this. The situation is this, I have a tree structure (an abstract syntax tree, specifically) and some nodes can contain child nodes of various types but all extended from a given base class.

I want to frequently do queries on this tree and I'd like to get back the specific subtypes I'm interested in. So I created a predicate class that I can then pass into a generic query method. At first I had a query method that looked like this:

public <T extends Element> List<T> findAll(IElementPredicate pred, Class<T> c);

where the Class argument was used just to indicate the return type. What bothered me about this approach is that all of my predicates were already for specific types so there is redundant information here. A typical call might look like:

List<Declaration> decls = 
    scope.findAll(new DeclarationPredicate(), Declaration.class);

So I refactored it like this:

public <T extends Element> List<T> findAll(IElementPredicate<T> pred);

Where the IElementPredicate interface looks like this:

public interface IElementPredicate<T extends Element> {
    public boolean match(T e);
    public String getDescription();
    public Class<T> getGenericClass();
}

The point here is that the predicate interface is expanded to provide the Class object instead. It makes writing the actual findAll method a little bit more work and it adds a bit more work in writing the predicate, but those are both essentially tiny "one-time" things and it makes the query call so much nicer because you don't have to add the extra (potentially redundant) argument, e.g.

List<Declaration> decls = scope.findAll(new DeclarationPredicate());

I haven't noticed this pattern before. Is this a typical way of dealing with the semantics of Java generics? Just curious if I'm missing some better pattern.

Commments?

UPDATE:

One question was what do you need the Class for? Here is the implementation of findAll:

public <T extends Element> List<T> findAll(IElementPredicate<T> pred) {
    List<T> ret = new LinkedList<T>();
    Class<T> c = pred.getGenericClass();
    for(Element e: elements) {
     if (!c.isInstance(e)) continue;
     T obj = c.cast(e);
     if (pred.match(obj)) {
      ret.add(c.cast(e));
     }
    }
    return ret;
}

While it is true that match only takes a T, I need to make sure the object is a T before I can call it. For that, I need the "isInstance" and "cast" methods of Class (as far as I can tell).

Answer 1

If you want, you can use the visitor pattern, or variants, to get around the explicit construction and casting. See the hibernate wiki page on this. I've been thinking about if you will get around your problem completely considering the peculiarities of type erasure, and I am not entirely sure it will work all the way.

edit: I saw your addition. If you would make your predicate hierarchy follow a visitor hierarchy, you wouldn't need the cast before the match call. Like so (untested):

interface Element {
    public boolean accept(ElementPredicateVisitor v);
}

class Declaration implements Element {
    public boolean accept(ElementPredicateVisitor v) {
        return v.visit(this);
    }    
}

class TaxReturn implements Element {
    public boolean accept(ElementPredicateVisitor v) {
        return v.visit(this);
    }    
}


interface IElementPredicate {
    public void match(Element e);
}

class ElementPredicateVisitor implements IElementPredicate {
    public boolean match(Element e) { 
        return e.accept(this); 
    }
    /**
     * default values
     */
    boolean visit(Declaration d) { return false; }
    boolean visit(TaxReturn tr) { return false; }
}

class DeclarationNamePredicate extends ElementPredicateVisitor {
    boolean visit(Declaration d) {
        return d.dSpecificExtraName() == "something"
    }
}

class TaxReturnSumPredicate extends ElementPredicateVisitor {
    boolean visit(TaxReturn tr) {
        return tr.sum() > 1000;
    }
}


public <T extends Element> List<T> findAll(IElementPredicate pred) {
    List<T> ret = new LinkedList<T>();
    for(Element e: elements) {            
        if (pred.match(obj)) {
                ret.add((T) obj);
        }
    }
    return ret;
}

Answer 2

Your tree structure sounds very much like an XML DOM object. Have you considered translating your tree into a DOM structure and using XPath to do your queries? It might be a lot less custom code.

Answer 3

I think that is nice and clean way of doing it and I would probably do it in the same way.

Answer 4

The closest "pattern" I think is type token and Generics Tutorial recommends them. You can also turn base predicate into super-type-token (a.k.a. Gafter gadget) and save the extra couple of lines when defining new predicates.