001: /*
002: * Created on Nov 9, 2005
003: */
004: package uk.org.ponder.rsf.request;
005:
006: import java.util.ArrayList;
007: import java.util.HashSet;
008: import java.util.List;
009:
010: import uk.org.ponder.beanutil.PathUtil;
011:
012: /** Applies a topological sorting to a collection of SubmittedValueEntry
013: * objects, such that any read or write of an entry of the bean model is
014: * scheduled after a write of a dependency. A dependency of an EL operation
015: * is a write to a path equal or higher to it in the bean hierarchy. Writes
016: * to the same path will currently be scheduled arbitrarily.
017: * @author Antranig Basman (antranig@caret.cam.ac.uk)
018: *
019: */
020: public class SVESorter {
021: // Notes on the topological sorting applied by this class.
022:
023: //Each entry is a WRITE to the EL path "valuebinding".
024: //In addition, a "fast EL" may represent a "read" from path newvalue,
025: //if newvalue represents an EL.
026: //Component binding: will WRITE to valuebinding ( when real value appears )
027: //EL: will WRITE to valuebinding, READ from newvalue.
028: //these READS must be shifted until AFTER writes of values related to newvalue.
029:
030: //i) a WRITE to a nested path DEPENDS ON a WRITE to a STRICTLY higher path.
031: //ii) a READ from a nested path DEPENDS ON a WRITE to a STRICTLY OR EQUAL higher path.
032: //iii) a WRITE to the SAME PATH should technically just replace the dependent write.
033:
034: //OK then. edge created FROM bean TO dependency, i.e. that which operates on higher path.
035: // WRITE READ
036: //e.g. valuebinding {permissionbean.name} value [field] NODE 1
037: //fast EL: {resource.a8394.permission} value {permissionbean} NODE 2
038: //edge FROM 2 -> 1
039: //hah. fast EL is actually SLOW!
040: RequestSubmittedValueCache rsvc;
041: ELDependencyMap elmap = new ELDependencyMap();
042: HashSet emitted = new HashSet();
043: ArrayList output = new ArrayList();
044:
045: public SVESorter(RequestSubmittedValueCache tosort) {
046: this .rsvc = tosort;
047:
048: for (int i = 0; i < rsvc.getEntries(); ++i) {
049: SubmittedValueEntry entry = rsvc.entryAt(i);
050: elmap.recordWrite(entry.valuebinding, entry);
051: if (entry.newvalue instanceof String) {
052: String readel = (String) entry.newvalue;
053: if (readel != null) {
054: elmap.recordRead(readel, entry);
055: }
056: }
057: }
058: }
059:
060: public List getSortedRSVC() {
061:
062: for (int i = 0; i < rsvc.getEntries(); ++i) {
063: SubmittedValueEntry entry = rsvc.entryAt(i);
064: if (!emitted.contains(entry)) {
065: attemptEvaluate(entry);
066: }
067: }
068: return output;
069: }
070:
071: private void attemptEvaluate(SubmittedValueEntry entry) {
072: emitted.add(entry);
073: String readpath = elmap.getReadPath(entry);
074: if (readpath != null) {
075: scheduleWrites(readpath);
076: }
077: String writepath = elmap.getWritePath(entry);
078: if (writepath != null) {
079: scheduleWrites(writepath);
080: }
081: output.add(entry);
082: }
083:
084: private void scheduleWrites(String writepath) {
085: // NB, the keeping of this on the stack results from being SURE that we
086: // can never recur to this path as a result of attemptEvaluate of
087: // a parent path (Even though we clearly do this as a result of fearing
088: // recurring to it from further up our *own* stack).
089: List writingbeans = elmap.getWriters(writepath);
090: if (writingbeans == ELDependencyMap.VALID_LIST_MARKER)
091: return;
092: // If we *write* a path, all pending *writes* to higher paths must already
093: // be done.
094: String parentpath = PathUtil.getToTailPath(writepath);
095: if (parentpath != null) {
096: scheduleWrites(parentpath);
097: }
098:
099: if (writingbeans != null) {
100: for (int i = 0; i < writingbeans.size(); ++i) {
101: SubmittedValueEntry sve = (SubmittedValueEntry) writingbeans
102: .get(i);
103: if (!emitted.contains(sve)) {
104: attemptEvaluate(sve);
105: }
106: }
107: elmap.recordPathValid(writepath);
108: }
109: }
110: }
|