1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17
18package com.android.internal.app;
19
20import android.app.usage.UsageStats;
21import android.app.usage.UsageStatsManager;
22import android.content.ComponentName;
23import android.content.Context;
24import android.content.Intent;
25import android.content.IntentFilter;
26import android.content.pm.ApplicationInfo;
27import android.content.pm.ComponentInfo;
28import android.content.pm.PackageManager;
29import android.content.pm.PackageManager.NameNotFoundException;
30import android.content.pm.ResolveInfo;
31import android.content.SharedPreferences;
32import android.content.ServiceConnection;
33import android.metrics.LogMaker;
34import android.os.Environment;
35import android.os.Handler;
36import android.os.IBinder;
37import android.os.Looper;
38import android.os.Message;
39import android.os.RemoteException;
40import android.os.storage.StorageManager;
41import android.os.UserHandle;
42import android.service.resolver.IResolverRankerService;
43import android.service.resolver.IResolverRankerResult;
44import android.service.resolver.ResolverRankerService;
45import android.service.resolver.ResolverTarget;
46import android.text.TextUtils;
47import android.util.ArrayMap;
48import android.util.Log;
49import com.android.internal.app.ResolverActivity.ResolvedComponentInfo;
50import com.android.internal.logging.MetricsLogger;
51import com.android.internal.logging.nano.MetricsProto.MetricsEvent;
52
53import java.io.File;
54import java.lang.InterruptedException;
55import java.text.Collator;
56import java.util.ArrayList;
57import java.util.Comparator;
58import java.util.concurrent.CountDownLatch;
59import java.util.concurrent.TimeUnit;
60import java.util.LinkedHashMap;
61import java.util.List;
62import java.util.Map;
63
64/**
65 * Ranks and compares packages based on usage stats.
66 */
67class ResolverComparator implements Comparator<ResolvedComponentInfo> {
68    private static final String TAG = "ResolverComparator";
69
70    private static final boolean DEBUG = false;
71
72    private static final int NUM_OF_TOP_ANNOTATIONS_TO_USE = 3;
73
74    // One week
75    private static final long USAGE_STATS_PERIOD = 1000 * 60 * 60 * 24 * 7;
76
77    private static final long RECENCY_TIME_PERIOD = 1000 * 60 * 60 * 12;
78
79    private static final float RECENCY_MULTIPLIER = 2.f;
80
81    // message types
82    private static final int RESOLVER_RANKER_SERVICE_RESULT = 0;
83    private static final int RESOLVER_RANKER_RESULT_TIMEOUT = 1;
84
85    // timeout for establishing connections with a ResolverRankerService.
86    private static final int CONNECTION_COST_TIMEOUT_MILLIS = 200;
87    // timeout for establishing connections with a ResolverRankerService, collecting features and
88    // predicting ranking scores.
89    private static final int WATCHDOG_TIMEOUT_MILLIS = 500;
90
91    private final Collator mCollator;
92    private final boolean mHttp;
93    private final PackageManager mPm;
94    private final UsageStatsManager mUsm;
95    private final Map<String, UsageStats> mStats;
96    private final long mCurrentTime;
97    private final long mSinceTime;
98    private final LinkedHashMap<ComponentName, ResolverTarget> mTargetsDict = new LinkedHashMap<>();
99    private final String mReferrerPackage;
100    private final Object mLock = new Object();
101    private ArrayList<ResolverTarget> mTargets;
102    private String mContentType;
103    private String[] mAnnotations;
104    private String mAction;
105    private ComponentName mResolvedRankerName;
106    private ComponentName mRankerServiceName;
107    private IResolverRankerService mRanker;
108    private ResolverRankerServiceConnection mConnection;
109    private AfterCompute mAfterCompute;
110    private Context mContext;
111    private CountDownLatch mConnectSignal;
112
113    private final Handler mHandler = new Handler(Looper.getMainLooper()) {
114        public void handleMessage(Message msg) {
115            switch (msg.what) {
116                case RESOLVER_RANKER_SERVICE_RESULT:
117                    if (DEBUG) {
118                        Log.d(TAG, "RESOLVER_RANKER_SERVICE_RESULT");
119                    }
120                    if (mHandler.hasMessages(RESOLVER_RANKER_RESULT_TIMEOUT)) {
121                        if (msg.obj != null) {
122                            final List<ResolverTarget> receivedTargets =
123                                    (List<ResolverTarget>) msg.obj;
124                            if (receivedTargets != null && mTargets != null
125                                    && receivedTargets.size() == mTargets.size()) {
126                                final int size = mTargets.size();
127                                boolean isUpdated = false;
128                                for (int i = 0; i < size; ++i) {
129                                    final float predictedProb =
130                                            receivedTargets.get(i).getSelectProbability();
131                                    if (predictedProb != mTargets.get(i).getSelectProbability()) {
132                                        mTargets.get(i).setSelectProbability(predictedProb);
133                                        isUpdated = true;
134                                    }
135                                }
136                                if (isUpdated) {
137                                    mRankerServiceName = mResolvedRankerName;
138                                }
139                            } else {
140                                Log.e(TAG, "Sizes of sent and received ResolverTargets diff.");
141                            }
142                        } else {
143                            Log.e(TAG, "Receiving null prediction results.");
144                        }
145                        mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT);
146                        mAfterCompute.afterCompute();
147                    }
148                    break;
149
150                case RESOLVER_RANKER_RESULT_TIMEOUT:
151                    if (DEBUG) {
152                        Log.d(TAG, "RESOLVER_RANKER_RESULT_TIMEOUT; unbinding services");
153                    }
154                    mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT);
155                    mAfterCompute.afterCompute();
156                    break;
157
158                default:
159                    super.handleMessage(msg);
160            }
161        }
162    };
163
164    public interface AfterCompute {
165        public void afterCompute ();
166    }
167
168    public ResolverComparator(Context context, Intent intent, String referrerPackage,
169                              AfterCompute afterCompute) {
170        mCollator = Collator.getInstance(context.getResources().getConfiguration().locale);
171        String scheme = intent.getScheme();
172        mHttp = "http".equals(scheme) || "https".equals(scheme);
173        mReferrerPackage = referrerPackage;
174        mAfterCompute = afterCompute;
175        mContext = context;
176
177        mPm = context.getPackageManager();
178        mUsm = (UsageStatsManager) context.getSystemService(Context.USAGE_STATS_SERVICE);
179
180        mCurrentTime = System.currentTimeMillis();
181        mSinceTime = mCurrentTime - USAGE_STATS_PERIOD;
182        mStats = mUsm.queryAndAggregateUsageStats(mSinceTime, mCurrentTime);
183        mContentType = intent.getType();
184        getContentAnnotations(intent);
185        mAction = intent.getAction();
186        mRankerServiceName = new ComponentName(mContext, this.getClass());
187    }
188
189    // get annotations of content from intent.
190    public void getContentAnnotations(Intent intent) {
191        ArrayList<String> annotations = intent.getStringArrayListExtra(
192                Intent.EXTRA_CONTENT_ANNOTATIONS);
193        if (annotations != null) {
194            int size = annotations.size();
195            if (size > NUM_OF_TOP_ANNOTATIONS_TO_USE) {
196                size = NUM_OF_TOP_ANNOTATIONS_TO_USE;
197            }
198            mAnnotations = new String[size];
199            for (int i = 0; i < size; i++) {
200                mAnnotations[i] = annotations.get(i);
201            }
202        }
203    }
204
205    public void setCallBack(AfterCompute afterCompute) {
206        mAfterCompute = afterCompute;
207    }
208
209    // compute features for each target according to usage stats of targets.
210    public void compute(List<ResolvedComponentInfo> targets) {
211        reset();
212
213        final long recentSinceTime = mCurrentTime - RECENCY_TIME_PERIOD;
214
215        float mostRecencyScore = 1.0f;
216        float mostTimeSpentScore = 1.0f;
217        float mostLaunchScore = 1.0f;
218        float mostChooserScore = 1.0f;
219
220        for (ResolvedComponentInfo target : targets) {
221            final ResolverTarget resolverTarget = new ResolverTarget();
222            mTargetsDict.put(target.name, resolverTarget);
223            final UsageStats pkStats = mStats.get(target.name.getPackageName());
224            if (pkStats != null) {
225                // Only count recency for apps that weren't the caller
226                // since the caller is always the most recent.
227                // Persistent processes muck this up, so omit them too.
228                if (!target.name.getPackageName().equals(mReferrerPackage)
229                        && !isPersistentProcess(target)) {
230                    final float recencyScore =
231                            (float) Math.max(pkStats.getLastTimeUsed() - recentSinceTime, 0);
232                    resolverTarget.setRecencyScore(recencyScore);
233                    if (recencyScore > mostRecencyScore) {
234                        mostRecencyScore = recencyScore;
235                    }
236                }
237                final float timeSpentScore = (float) pkStats.getTotalTimeInForeground();
238                resolverTarget.setTimeSpentScore(timeSpentScore);
239                if (timeSpentScore > mostTimeSpentScore) {
240                    mostTimeSpentScore = timeSpentScore;
241                }
242                final float launchScore = (float) pkStats.mLaunchCount;
243                resolverTarget.setLaunchScore(launchScore);
244                if (launchScore > mostLaunchScore) {
245                    mostLaunchScore = launchScore;
246                }
247
248                float chooserScore = 0.0f;
249                if (pkStats.mChooserCounts != null && mAction != null
250                        && pkStats.mChooserCounts.get(mAction) != null) {
251                    chooserScore = (float) pkStats.mChooserCounts.get(mAction)
252                            .getOrDefault(mContentType, 0);
253                    if (mAnnotations != null) {
254                        final int size = mAnnotations.length;
255                        for (int i = 0; i < size; i++) {
256                            chooserScore += (float) pkStats.mChooserCounts.get(mAction)
257                                    .getOrDefault(mAnnotations[i], 0);
258                        }
259                    }
260                }
261                if (DEBUG) {
262                    if (mAction == null) {
263                        Log.d(TAG, "Action type is null");
264                    } else {
265                        Log.d(TAG, "Chooser Count of " + mAction + ":" +
266                                target.name.getPackageName() + " is " +
267                                Float.toString(chooserScore));
268                    }
269                }
270                resolverTarget.setChooserScore(chooserScore);
271                if (chooserScore > mostChooserScore) {
272                    mostChooserScore = chooserScore;
273                }
274            }
275        }
276
277        if (DEBUG) {
278            Log.d(TAG, "compute - mostRecencyScore: " + mostRecencyScore
279                    + " mostTimeSpentScore: " + mostTimeSpentScore
280                    + " mostLaunchScore: " + mostLaunchScore
281                    + " mostChooserScore: " + mostChooserScore);
282        }
283
284        mTargets = new ArrayList<>(mTargetsDict.values());
285        for (ResolverTarget target : mTargets) {
286            final float recency = target.getRecencyScore() / mostRecencyScore;
287            setFeatures(target, recency * recency * RECENCY_MULTIPLIER,
288                    target.getLaunchScore() / mostLaunchScore,
289                    target.getTimeSpentScore() / mostTimeSpentScore,
290                    target.getChooserScore() / mostChooserScore);
291            addDefaultSelectProbability(target);
292            if (DEBUG) {
293                Log.d(TAG, "Scores: " + target);
294            }
295        }
296        predictSelectProbabilities(mTargets);
297    }
298
299    @Override
300    public int compare(ResolvedComponentInfo lhsp, ResolvedComponentInfo rhsp) {
301        final ResolveInfo lhs = lhsp.getResolveInfoAt(0);
302        final ResolveInfo rhs = rhsp.getResolveInfoAt(0);
303
304        // We want to put the one targeted to another user at the end of the dialog.
305        if (lhs.targetUserId != UserHandle.USER_CURRENT) {
306            return rhs.targetUserId != UserHandle.USER_CURRENT ? 0 : 1;
307        }
308        if (rhs.targetUserId != UserHandle.USER_CURRENT) {
309            return -1;
310        }
311
312        if (mHttp) {
313            // Special case: we want filters that match URI paths/schemes to be
314            // ordered before others.  This is for the case when opening URIs,
315            // to make native apps go above browsers.
316            final boolean lhsSpecific = ResolverActivity.isSpecificUriMatch(lhs.match);
317            final boolean rhsSpecific = ResolverActivity.isSpecificUriMatch(rhs.match);
318            if (lhsSpecific != rhsSpecific) {
319                return lhsSpecific ? -1 : 1;
320            }
321        }
322
323        final boolean lPinned = lhsp.isPinned();
324        final boolean rPinned = rhsp.isPinned();
325
326        if (lPinned && !rPinned) {
327            return -1;
328        } else if (!lPinned && rPinned) {
329            return 1;
330        }
331
332        // Pinned items stay stable within a normal lexical sort and ignore scoring.
333        if (!lPinned && !rPinned) {
334            if (mStats != null) {
335                final ResolverTarget lhsTarget = mTargetsDict.get(new ComponentName(
336                        lhs.activityInfo.packageName, lhs.activityInfo.name));
337                final ResolverTarget rhsTarget = mTargetsDict.get(new ComponentName(
338                        rhs.activityInfo.packageName, rhs.activityInfo.name));
339
340                if (lhsTarget != null && rhsTarget != null) {
341                    final int selectProbabilityDiff = Float.compare(
342                        rhsTarget.getSelectProbability(), lhsTarget.getSelectProbability());
343
344                    if (selectProbabilityDiff != 0) {
345                        return selectProbabilityDiff > 0 ? 1 : -1;
346                    }
347                }
348            }
349        }
350
351        CharSequence  sa = lhs.loadLabel(mPm);
352        if (sa == null) sa = lhs.activityInfo.name;
353        CharSequence  sb = rhs.loadLabel(mPm);
354        if (sb == null) sb = rhs.activityInfo.name;
355
356        return mCollator.compare(sa.toString().trim(), sb.toString().trim());
357    }
358
359    public float getScore(ComponentName name) {
360        final ResolverTarget target = mTargetsDict.get(name);
361        if (target != null) {
362            return target.getSelectProbability();
363        }
364        return 0;
365    }
366
367    public void updateChooserCounts(String packageName, int userId, String action) {
368        if (mUsm != null) {
369            mUsm.reportChooserSelection(packageName, userId, mContentType, mAnnotations, action);
370        }
371    }
372
373    // update ranking model when the connection to it is valid.
374    public void updateModel(ComponentName componentName) {
375        synchronized (mLock) {
376            if (mRanker != null) {
377                try {
378                    int selectedPos = new ArrayList<ComponentName>(mTargetsDict.keySet())
379                            .indexOf(componentName);
380                    if (selectedPos >= 0 && mTargets != null) {
381                        final float selectedProbability = getScore(componentName);
382                        int order = 0;
383                        for (ResolverTarget target : mTargets) {
384                            if (target.getSelectProbability() > selectedProbability) {
385                                order++;
386                            }
387                        }
388                        logMetrics(order);
389                        mRanker.train(mTargets, selectedPos);
390                    } else {
391                        if (DEBUG) {
392                            Log.d(TAG, "Selected a unknown component: " + componentName);
393                        }
394                    }
395                } catch (RemoteException e) {
396                    Log.e(TAG, "Error in Train: " + e);
397                }
398            } else {
399                if (DEBUG) {
400                    Log.d(TAG, "Ranker is null; skip updateModel.");
401                }
402            }
403        }
404    }
405
406    // unbind the service and clear unhandled messges.
407    public void destroy() {
408        mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT);
409        mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT);
410        if (mConnection != null) {
411            mContext.unbindService(mConnection);
412            mConnection.destroy();
413        }
414        if (DEBUG) {
415            Log.d(TAG, "Unbinded Resolver Ranker.");
416        }
417    }
418
419    // records metrics for evaluation.
420    private void logMetrics(int selectedPos) {
421        if (mRankerServiceName != null) {
422            MetricsLogger metricsLogger = new MetricsLogger();
423            LogMaker log = new LogMaker(MetricsEvent.ACTION_TARGET_SELECTED);
424            log.setComponentName(mRankerServiceName);
425            int isCategoryUsed = (mAnnotations == null) ? 0 : 1;
426            log.addTaggedData(MetricsEvent.FIELD_IS_CATEGORY_USED, isCategoryUsed);
427            log.addTaggedData(MetricsEvent.FIELD_RANKED_POSITION, selectedPos);
428            metricsLogger.write(log);
429        }
430    }
431
432    // connect to a ranking service.
433    private void initRanker(Context context) {
434        synchronized (mLock) {
435            if (mConnection != null && mRanker != null) {
436                if (DEBUG) {
437                    Log.d(TAG, "Ranker still exists; reusing the existing one.");
438                }
439                return;
440            }
441        }
442        Intent intent = resolveRankerService();
443        if (intent == null) {
444            return;
445        }
446        mConnectSignal = new CountDownLatch(1);
447        mConnection = new ResolverRankerServiceConnection(mConnectSignal);
448        context.bindServiceAsUser(intent, mConnection, Context.BIND_AUTO_CREATE, UserHandle.SYSTEM);
449    }
450
451    // resolve the service for ranking.
452    private Intent resolveRankerService() {
453        Intent intent = new Intent(ResolverRankerService.SERVICE_INTERFACE);
454        final List<ResolveInfo> resolveInfos = mPm.queryIntentServices(intent, 0);
455        for (ResolveInfo resolveInfo : resolveInfos) {
456            if (resolveInfo == null || resolveInfo.serviceInfo == null
457                    || resolveInfo.serviceInfo.applicationInfo == null) {
458                if (DEBUG) {
459                    Log.d(TAG, "Failed to retrieve a ranker: " + resolveInfo);
460                }
461                continue;
462            }
463            ComponentName componentName = new ComponentName(
464                    resolveInfo.serviceInfo.applicationInfo.packageName,
465                    resolveInfo.serviceInfo.name);
466            try {
467                final String perm = mPm.getServiceInfo(componentName, 0).permission;
468                if (!ResolverRankerService.BIND_PERMISSION.equals(perm)) {
469                    Log.w(TAG, "ResolverRankerService " + componentName + " does not require"
470                            + " permission " + ResolverRankerService.BIND_PERMISSION
471                            + " - this service will not be queried for ResolverComparator."
472                            + " add android:permission=\""
473                            + ResolverRankerService.BIND_PERMISSION + "\""
474                            + " to the <service> tag for " + componentName
475                            + " in the manifest.");
476                    continue;
477                }
478                if (PackageManager.PERMISSION_GRANTED != mPm.checkPermission(
479                        ResolverRankerService.HOLD_PERMISSION,
480                        resolveInfo.serviceInfo.packageName)) {
481                    Log.w(TAG, "ResolverRankerService " + componentName + " does not hold"
482                            + " permission " + ResolverRankerService.HOLD_PERMISSION
483                            + " - this service will not be queried for ResolverComparator.");
484                    continue;
485                }
486            } catch (NameNotFoundException e) {
487                Log.e(TAG, "Could not look up service " + componentName
488                        + "; component name not found");
489                continue;
490            }
491            if (DEBUG) {
492                Log.d(TAG, "Succeeded to retrieve a ranker: " + componentName);
493            }
494            mResolvedRankerName = componentName;
495            intent.setComponent(componentName);
496            return intent;
497        }
498        return null;
499    }
500
501    // set a watchdog, to avoid waiting for ranking service for too long.
502    private void startWatchDog(int timeOutLimit) {
503        if (DEBUG) Log.d(TAG, "Setting watchdog timer for " + timeOutLimit + "ms");
504        if (mHandler == null) {
505            Log.d(TAG, "Error: Handler is Null; Needs to be initialized.");
506        }
507        mHandler.sendEmptyMessageDelayed(RESOLVER_RANKER_RESULT_TIMEOUT, timeOutLimit);
508    }
509
510    private class ResolverRankerServiceConnection implements ServiceConnection {
511        private final CountDownLatch mConnectSignal;
512
513        public ResolverRankerServiceConnection(CountDownLatch connectSignal) {
514            mConnectSignal = connectSignal;
515        }
516
517        public final IResolverRankerResult resolverRankerResult =
518                new IResolverRankerResult.Stub() {
519            @Override
520            public void sendResult(List<ResolverTarget> targets) throws RemoteException {
521                if (DEBUG) {
522                    Log.d(TAG, "Sending Result back to Resolver: " + targets);
523                }
524                synchronized (mLock) {
525                    final Message msg = Message.obtain();
526                    msg.what = RESOLVER_RANKER_SERVICE_RESULT;
527                    msg.obj = targets;
528                    mHandler.sendMessage(msg);
529                }
530            }
531        };
532
533        @Override
534        public void onServiceConnected(ComponentName name, IBinder service) {
535            if (DEBUG) {
536                Log.d(TAG, "onServiceConnected: " + name);
537            }
538            synchronized (mLock) {
539                mRanker = IResolverRankerService.Stub.asInterface(service);
540                mConnectSignal.countDown();
541            }
542        }
543
544        @Override
545        public void onServiceDisconnected(ComponentName name) {
546            if (DEBUG) {
547                Log.d(TAG, "onServiceDisconnected: " + name);
548            }
549            synchronized (mLock) {
550                destroy();
551            }
552        }
553
554        public void destroy() {
555            synchronized (mLock) {
556                mRanker = null;
557            }
558        }
559    }
560
561    private void reset() {
562        mTargetsDict.clear();
563        mTargets = null;
564        mRankerServiceName = new ComponentName(mContext, this.getClass());
565        mResolvedRankerName = null;
566        startWatchDog(WATCHDOG_TIMEOUT_MILLIS);
567        initRanker(mContext);
568    }
569
570    // predict select probabilities if ranking service is valid.
571    private void predictSelectProbabilities(List<ResolverTarget> targets) {
572        if (mConnection == null) {
573            if (DEBUG) {
574                Log.d(TAG, "Has not found valid ResolverRankerService; Skip Prediction");
575            }
576            return;
577        } else {
578            try {
579                mConnectSignal.await(CONNECTION_COST_TIMEOUT_MILLIS, TimeUnit.MILLISECONDS);
580                synchronized (mLock) {
581                    if (mRanker != null) {
582                        mRanker.predict(targets, mConnection.resolverRankerResult);
583                        return;
584                    } else {
585                        if (DEBUG) {
586                            Log.d(TAG, "Ranker has not been initialized; skip predict.");
587                        }
588                    }
589                }
590            } catch (InterruptedException e) {
591                Log.e(TAG, "Error in Wait for Service Connection.");
592            } catch (RemoteException e) {
593                Log.e(TAG, "Error in Predict: " + e);
594            }
595        }
596        if (mAfterCompute != null) {
597            mAfterCompute.afterCompute();
598        }
599    }
600
601    // adds select prob as the default values, according to a pre-trained Logistic Regression model.
602    private void addDefaultSelectProbability(ResolverTarget target) {
603        float sum = 2.5543f * target.getLaunchScore() + 2.8412f * target.getTimeSpentScore() +
604                0.269f * target.getRecencyScore() + 4.2222f * target.getChooserScore();
605        target.setSelectProbability((float) (1.0 / (1.0 + Math.exp(1.6568f - sum))));
606    }
607
608    // sets features for each target
609    private void setFeatures(ResolverTarget target, float recencyScore, float launchScore,
610                             float timeSpentScore, float chooserScore) {
611        target.setRecencyScore(recencyScore);
612        target.setLaunchScore(launchScore);
613        target.setTimeSpentScore(timeSpentScore);
614        target.setChooserScore(chooserScore);
615    }
616
617    static boolean isPersistentProcess(ResolvedComponentInfo rci) {
618        if (rci != null && rci.getCount() > 0) {
619            return (rci.getResolveInfoAt(0).activityInfo.applicationInfo.flags &
620                    ApplicationInfo.FLAG_PERSISTENT) != 0;
621        }
622        return false;
623    }
624}
625