native/src/com/android/commands/monkey/ape/jev/JevRegion.java
51:         final long abstraction,topology,concretes,facts;final int current;final String tree;
52:         final List<Fact> states;final List<Link> links;final Set<Integer> roots;final List<Concrete> entries;
53:         Snapshot(long a,long t,long c,long f,int cur,String tr,List<Fact> s,List<Link> l,Set<Integer> r,List<Concrete> e){
54:             abstraction=a;topology=t;concretes=c;facts=f;current=cur;tree=tr;
55:             states=Collections.unmodifiableList(new ArrayList<Fact>(s));links=Collections.unmodifiableList(new ArrayList<Link>(l));
56:             roots=Collections.unmodifiableSet(new HashSet<Integer>(r));entries=Collections.unmodifiableList(new ArrayList<Concrete>(e));
57:         }
58:     }
59:     static final class Result {
60:         final Snapshot input;final Set<Integer> blocked,isolated,members;final List<Set<Integer>> regions;final String reason;final long nanos,dominatorNanos,summaryNanos,reachabilityNanos;
61:         Result(Snapshot s,Set<Integer>b,Set<Integer>i,Set<Integer>m,List<Set<Integer>> regions,String r,long n,long d,long a,long reach){
62:             input=s;blocked=Collections.unmodifiableSet(b);isolated=Collections.unmodifiableSet(i);members=Collections.unmodifiableSet(m);
63:             List<Set<Integer>> copy=new ArrayList<Set<Integer>>();for(Set<Integer> region:regions)copy.add(Collections.unmodifiableSet(new HashSet<Integer>(region)));
64:             this.regions=Collections.unmodifiableList(copy);reason=r;nanos=n;dominatorNanos=d;summaryNanos=a;reachabilityNanos=reach;
65:         }
66:     }
67:     /** Tree reuse depends only on confirmed State connections and real roots, never strength. */
68:     static final class Calculator {
69:         long abstraction=-1,topology=-1;BitSet[] dominators;BitSet reachable;
70:         int[] parents;List<List<Integer>> children;List<Integer> order;
71:         void prepare(Snapshot s) {
72:             int n=s.states.size();
73:             if(abstraction!=s.abstraction || topology!=s.topology) {
74:                 reachable=reach(s,s.roots,Collections.<Integer>emptySet());dominators=new BitSet[n];
75:                 for(int i=0;i<n;i++){dominators[i]=new BitSet(n);if(reachable.get(i)){dominators[i].or(reachable);if(s.roots.contains(i)){dominators[i].clear();dominators[i].set(i);}}}
76:                 List<List<Integer>> predecessors=new ArrayList<List<Integer>>();for(int i=0;i<n;i++)predecessors.add(new ArrayList<Integer>());
77:                 for(Link l:s.links)if(reachable.get(l.source))predecessors.get(l.target).add(l.source);
78:                 boolean changed;
79:                 do {changed=false;for(int v=0;v<n;v++)if(reachable.get(v) && !s.roots.contains(v)) {
80:                     checkInterrupted();BitSet d=(BitSet)reachable.clone();
81:                     for(int p:predecessors.get(v))d.and(dominators[p]);
82:                     d.set(v);if(!d.equals(dominators[v])){dominators[v]=d;changed=true;}
83:                 }}while(changed);
84:                 parents=new int[n];Arrays.fill(parents,-1);children=new ArrayList<List<Integer>>();order=new ArrayList<Integer>();
85:                 for(int i=0;i<n;i++)children.add(new ArrayList<Integer>());
86:                 for(int v=0;v<n;v++)if(reachable.get(v)) {
87:                     checkInterrupted();int depth=-1;
88:                     for(int d=dominators[v].nextSetBit(0);d>=0;d=dominators[v].nextSetBit(d+1))if(d!=v && dominators[d].cardinality()>depth){parents[v]=d;depth=dominators[d].cardinality();}
89:                     if(parents[v]>=0)children.get(parents[v]).add(v);
90:                 }
91:                 for(int v=0;v<n;v++)if(reachable.get(v) && parents[v]<0)order.add(v);
92:                 for(int i=0;i<order.size();i++)order.addAll(children.get(order.get(i)));
93:                 abstraction=s.abstraction;topology=s.topology;
94:             }
95:         }
96:         /** All non-entry dominator subtrees, independent of exploration facts. */
97:         List<JevRegionLocator.Region> structure(Snapshot s) {
98:             prepare(s);List<JevRegionLocator.Region> regions=new ArrayList<JevRegionLocator.Region>();
99:             for(int d:order)if(!s.roots.contains(d)) {
100:                 Set<Integer> members=new TreeSet<Integer>();ArrayDeque<Integer> queue=new ArrayDeque<Integer>();queue.add(d);
101:                 while(!queue.isEmpty()){checkInterrupted();int v=queue.remove();members.add(v);queue.addAll(children.get(v));}
102:                 regions.add(new JevRegionLocator.Region(d,members));
103:             }
104:             return regions;
105:         }
106:         Result compute(Snapshot s) {
107:             long start=System.nanoTime();prepare(s);int n=s.states.size();
108:             long dominatorNanos=System.nanoTime()-start,summaryStart=System.nanoTime();
109:             boolean[] complete=new boolean[n];
110:             for(int i=order.size()-1;i>=0;i--){checkInterrupted();int v=order.get(i);complete[v]=s.states.get(v).complete();for(int child:children.get(v))complete[v] &= complete[child];}
111:             Set<Integer> union=new HashSet<Integer>();List<Set<Integer>> regions=new ArrayList<Set<Integer>>();
112:             for(int d:order)if(!s.roots.contains(d) && complete[d] && !union.contains(d)) {
113:                 Set<Integer> members=new HashSet<Integer>();ArrayDeque<Integer> queue=new ArrayDeque<Integer>();queue.add(d);
114:                 while(!queue.isEmpty()){int v=queue.remove();members.add(v);queue.addAll(children.get(v));}
115:                 regions.add(members);union.addAll(members);
116:             }
117:             return validate(s,regions,null,start,dominatorNanos,System.nanoTime()-summaryStart);
118:         }
119:     }
120:     /** Shared entry/exit checks for worker proposals and current-fact revalidation; no new dominator search. */
121:     private static Result validate(Snapshot s,List<Set<Integer>> proposed,Set<Integer> permitted,long start,long dominatorNanos,long summaryNanos) {

native/src/com/android/commands/monkey/ape/model/Graph.java
190:             }
191:         }
192:         return true;
193:     }
194: 
195:     public void setVerbose(boolean verbose) {
196:         this.verbose = verbose;
197:     }
198: 
199:     public void setVersion(int version) {
200:         graphId = "g" + version;
201:     }
202: 
203:     public ActivityNode getActivityNode(String activity) {
204:         ActivityNode node = activities.get(activity);
205:         return node;

native/src/com/android/commands/monkey/ape/model/Graph.java
245:     }
246: 
247:     public State getOrCreateState(StateKey stateKey) {
248:         State state = keyToState.get(stateKey);
249:         if (state == null) {
250:             state = State.buildState(stateKey);
251:             state.setGraphId(graphId + "s" + stateCounter++);
252:             //Logger.dformat("Try to add state " + state.getGraphId() + " " + state.getStateKey());
253:             fireNewStateEvents(state);
254:             State check = keyToState.put(stateKey, state);
255:             if (check != null) {
256:                 state.dumpState();
257:                 check.dumpState();
258:                 throw new IllegalStateException("Impossible: two state has the same key: " + state.getStateKey());
259:             }
260:             check = idToState.put(state.getGraphId(), state);
261:             if (check != null) {
262:                 state.dumpState();
263:                 check.dumpState();
264:                 throw new IllegalStateException("Impossible: two state has the same id: " + state.getGraphId());
265:             }
266:             addActivity(state);
267:             addActions(state);
268:             Utils.addToMapSet(namingToStates, state.getCurrentNaming(), state);
269:         }
270:         return state;
271:     }
272: 
273:     private void addActions(State state) {
274:         Map<Name, Set<ModelAction>> actions = Utils.getMapFromMap(nameToActions, state.getActivity());
275:         for (ModelAction action : state.getActions()) {
276:             action.setGraphId(graphId + "a" + actionCounters.getTotal());
277:             actionCounters.logEvent(action.getType());
278:             unvisitedActions.add(action);
279:             if (action.requireTarget()) {
280:                 Utils.addToMapSet(actions, action.getTarget(), action);
281:             }
282:         }
283:     }
284: 
285:     static Comparator<GraphElement> LAST_VISIT_COUNT_COMPARATOR = new Comparator<GraphElement>() {

native/src/com/android/commands/monkey/ape/model/Graph.java
375:             GUITreeAction treeAction, GUITree targetTree) {
376:         StateTransition edge = addStateTransition(source, action, target);
377:         if (edge == null) {
378:             return null;
379:         }
380:         GUITreeTransition treeTransition = new GUITreeTransition(sourceTree, treeAction, targetTree);
381:         treeTransition.setThrottle(action.getThrottle());
382:         edge.updateThrottle(treeTransition.getThrottle());
383:         stateTransitionHistory.add(edge);
384:         treeTransitionHistory.add(treeTransition);
385:         edge.append(treeTransition);
386: 
387:         edge.strengthen();
388:         markVisited(edge, timestamp);
389:         fireStateTransitionEvents(edge);
390:         if (this.entryGUITrees.contains(sourceTree)) {
391:             this.entryStates.add(source);
392:         }
393:         if (this.cleanEntryGUITrees.contains(sourceTree)) {
394:             this.cleanEntryStates.add(source);
395:         }
396:         return edge;
397:     }
398: 
399:     public StateTransition addTransition(State source, ModelAction action, State target, GUITreeTransition treeTransition) {
400:         StateTransition edge = addStateTransition(source, action, target);
401:         if (edge == null) {
402:             throw new IllegalStateException("Should not be null.");
403:         }
404:         if (this.entryGUITrees.contains(treeTransition.getSource())) {
405:             this.entryStates.add(source);
406:         }
407:         if (this.cleanEntryGUITrees.contains(treeTransition.getSource())) {
408:             this.cleanEntryStates.add(source);
409:         }
410:         edge.strengthen();
411:         stateTransitionHistory.add(edge);
412:         edge.updateThrottle(treeTransition.getThrottle());

native/src/com/android/commands/monkey/ape/model/Graph.java
860:     }
861: 
862:     public void addEntryGUITree(GUITree tree) {
863:         this.entryGUITrees.add(tree);
864:     }
865: 
866:     public void addCleanEntryGUITree(GUITree tree) {
867:         this.cleanEntryGUITrees.add(tree);
868:     }
869: 
870:     public boolean isEntryState(State state) {
871:         return this.entryStates.contains(state);
872:     }
873: 
874:     public boolean isCleanEntryState(State state) {
875:         return this.cleanEntryStates.contains(state);

native/src/com/android/commands/monkey/ape/agent/StatefulAgent.java
660:         currentGUITreeAction = guiAction;
661:         Logger.iprintln("Recover current states and actions...");
662:         Logger.iformat("> recovered current state: %s", currentState);
663:         Logger.iformat("> recovered current action: %s", currentAction);
664:         currentStateRecovered = true;
665:     }
666: 
667:     protected void updateGraph() {
668:         if (currentState == null) {
669:             if (this.appActivityJustStarted) {
670:                 Logger.iformat("Entry state: %s", newState);
671:                 model.getGraph().addEntryGUITree(newGUITree);
672:                 if(jev!=null)jev.regionRoot(newState);
673:                 if (appActivityJustStartedFromClean) {
674:                     model.getGraph().addCleanEntryGUITree(newGUITree);
675:                 }
676:                 this.appActivityJustStartedFromClean = false;
677:                 this.appActivityJustStarted = false;
678:             }
679:         }
680:         currentStateTransition = model.addTransition(currentState, currentAction, newState, currentGUITree,
681:                 currentGUITreeAction, newGUITree);
682:         if (jev != null) jev.sync(model, getTimestamp());
683:         checkStable();
684:     }
685: 
686:     protected void checkStable() {
687:         Logger.format("Graph Stable Counter: graph (%d), state (%d), activity (%d)", graphStableCounter,
688:                 stateStableCounter, activityStableCounter);
689:         if (graphStableCounter > 0) {

native/src/com/android/commands/monkey/ape/jev/JevRegistry.java
360:         if(state==null || action==null || tree==null || node==null || tree.getCurrentState()!=state)return false;
361:         long profileStart=JevReviewProfile.start();
362:         try {GUITreeAction candidate=new GUITreeAction(tree,node,action);
363:             return hardMatch(candidate)!=null || confirmedExact(candidate);
364:         } finally {JevReviewProfile.end("exact_execution_filter",profileStart);}
365:     }
366: 
367:     /** Confirmed concrete execution in any State of the same activity. */
368:     public boolean hasRelatedConcreteExecution(String actionType,String sourceActivity,String canonicalFullName) {
369:         if(actionType==null || sourceActivity==null || canonicalFullName==null || canonicalFullName.length()==0)return false;
370:         ConcreteActionIdentity identity=new ConcreteActionIdentity(actionType,canonicalFullName);
371:         List<Execution> values=relatedIndex.get(relatedKey(sourceActivity,identity));
372:         if(values!=null && !values.isEmpty())return true;
373:         // Input may be confirmed before its transition is observed/indexed.
374:         // Consult the existing authority; do not invent another history index.
375:         for(GUITreeAction input:confirmedInputs) {
376:             if(input.getGUITreeNode()!=null && confirmedMappingProblem(input)==null && input.getActionType().name().equals(actionType)
377:                     && sourceActivity.equals(input.getModelAction().getState().getActivity())
378:                     && identity.equals(ConcreteActionIdentity.of(actionType,input.getGUITreeNode())))return true;
379:         }
380:         return false;
381:     }
382:     private static String relatedKey(String activity,ConcreteActionIdentity identity) {
383:         return new JSONArray().put(identity.actionType()).put(activity).put(identity.canonicalFullName()).toString();
384:     }
385:     public List<Entry> suggestions() {
386:         List<Entry> out=new ArrayList<Entry>();
387:         for(Entry e:audits.values())if(probeAvailable(e))out.add(e);

native/src/com/android/commands/monkey/ape/jev/JevRegistry.java
800:         }
801:     }
802:     private boolean related(Execution e,String actionType,String sourceActivity,Member candidate) {
803:         if(!e.member.type.equals(actionType))return false;
804:         if(!e.sourceActivities.contains(sourceActivity==null?"":sourceActivity))return false;
805:         return !e.member.fullName.isEmpty() && new ConcreteActionIdentity(e.member.type,e.member.fullName)
806:             .equals(new ConcreteActionIdentity(actionType,candidate.fullName));
807:     }
808:     private boolean relatedToAny(Execution e,String actionType,String sourceActivity,List<Member> candidates) {
809:         for(Member candidate:candidates)if(related(e,actionType,sourceActivity,candidate))return true;
810:         return false;
811:     }
812:     private boolean sameStateAction(Execution e,String actionType,State state,ModelAction modelAction) {
813:         if(e.anchor==null || !belongsToState(state,e.anchor.tree) || !e.member.type.equals(actionType))return false;
814:         return modelAction!=null && e.concreteAction!=null && e.concreteAction.getModelAction()==modelAction;
815:     }
816:     private boolean belongsToState(State state,GUITree tree) {
817:         if(state==null || tree==null)return false;
818:         for(GUITree candidate:state.getGUITrees())if(candidate==tree)return true;
819:         return false;
820:     }
821:     private JSONArray history(List<GUITreeAction> currentActions,String actionType,String sourceActivity,State state,ModelAction modelAction,List<Member> candidates,List<Execution> selected,JSONObject contexts) throws JSONException {
822:         List<Execution> sameStateAction=new ArrayList<Execution>(), relatedOther=new ArrayList<Execution>();
823:         Set<Execution> relevant=Collections.newSetFromMap(new IdentityHashMap<Execution,Boolean>());
824:         if(!currentActions.isEmpty())relevant.addAll(indexed(executionIndex,currentActions.get(0)));
825:         for(Member member:candidates) {
826:             List<Execution> related=relatedIndex.get(relatedKey(sourceActivity==null?"":sourceActivity,
827:                 new ConcreteActionIdentity(actionType,member.fullName)));
828:             if(related!=null)relevant.addAll(related);
829:         }
830:         for(Execution e:relevant) {
831:             boolean current=false;
832:             for(GUITreeAction action:currentActions)if(sameConcrete(action,e.concreteAction)){current=true;break;}
833:             if(current)continue;
834:             if(sameStateAction(e,actionType,state,modelAction))sameStateAction.add(e);
835:             else if(belongsToState(state,e.anchor.tree))continue;
836:             else if(relatedToAny(e,actionType,sourceActivity,candidates))relatedOther.add(e);
837:         }