Overview of Content
如有引用參考請詳註出處，感謝
本文探討了 Interpreter 解譯器模式在 Android Framework 中的應用與實現
首先介紹了 Interpreter 解釋器的定義，包括形式語言中的符號以及其在不同場景下的使用情況。接著，通過解釋 Interpreter 的定義和使用 UML 圖表，深入分析了其設計的優缺點。在實現方面，文章討論了標準實現中的加減運算以及利用堆疊（Stack）來進行計算的技術
此外，還介紹了 Android 源碼中相關部分，如 PakageParser2 的解析過程、ParsingPackageUtils 的解析工具以及解析 AndroidManifest 中 Application 標籤的過程，以及 ParsingPackageImpl 如何儲存 Package 訊息。透過本文，讀者將能深入了解 Interpreter 模式在 Android Framework 中的實際應用與相關源碼實現。
Interpreter 解釋器定義
● 重複發生的問題，並且問題可以簡單分為終端、非終端
● 通常可使用在 自定義語言的解析，定義語言的 形式
大多數是定義形式語言，但也是可以用來描述語言、文法 (但 Scope 就比較大)
形式語言：符號
● 形式語言：以下我們假設定義兩個符號，這兩個符號代表的意義如下
● ::=：表示可推導
● *：表示閉包（Closure）
# 來解釋以下這兩行形式語言
- S ::= abA*ef
- A ::= cd
● 先看 S :== abA*ef，其中有 A 符號，下一行則會定義 A ::= cd
● 因此可以把定義帶入，S 推導為 S :== ab(cd)*ef，使用正規表達來看，ab 之間的 cd 符號可以有 0~N 個，最後才是 ef 符號，以下定義則都成立
## 以正則表達式的角度去看
## abef 之間有 0 個 cd
abef
## abef 之間有 1 個 cd
abcdef
## abef 之間有 3 個 cd
abcdcdcdef
● 終端符號：無法再被推導的符號 (可再找到來源)，從上面我們可以知道
| 符號 | 是否是終端符號 | 說明 |
|---|---|---|
| ab | Y | 不可再被推導 |
| cd | Y | 不可再被推導 |
| ef | Y | 不可再被推導 |
| S | N | 可推導出右邊表達式 |
| A | N | 可推導出右邊表達式 |
● 初始符號
由於整個推導式是從
S開始，所以S也稱為 初始符號
Interpreter 使用場景
A. 一個語言，可以將該語句表達為一個 抽象語法樹 時；像是解釋 a + b - c語法時… 其中可以知道
- 終端符號：
a、b、c符號
- 非終端符號：
+、-符號
B. 特定領域的重複問題；ABC 轉為 abc ，這些符號全部都是終端符號
- 終端符號：
A、B、C、a、b、c符號
C. 直譯器定義了一個表達式介面，透過該介面直譯一個上下文，可透過資料結構的Tree、Stack 建構
Interpreter 定義 & Interpreter UML
● Interpreter 定義
給一門語言定義它的語法的一種表示，並給定一個解釋器來解釋該語言的語法
● Interpreter UML 如下
| 類 | 功能 |
|---|---|
AbstractExoression | 抽象表達式，定義抽象直譯方法，讓子類實做 |
TerminalExoression | 終端終結表達式 |
NonTerminalExoression | 繼承 AbstractExoression，並聚合 AbstractExoression |
●
NonTerminalExoression使用依賴倒置的概念，讓抽象依賴於抽象
Interpreter 設計：優缺點
● Interpreter 設計優點 :
對於每個符號的擴充性極高，文法易新增
● Interpreter 設計缺點 :
● 每個文法建立一個類別做處理，所以 不適合大量複雜的文法
● 類的膨脹
● 解釋器模式採用遞歸調用
● 會導致程式的可讀性降低、複查性提昇 (遞歸就是如此)
● 同時導致效率不佳
Interpreter 實現
標準實現：加減運算
A. AbstractExoression 類：AbstractExpression 提取所有解釋器的共同行為作為抽象，這裡宣告解釋器都必須返回 int
// AbstractExoression 類
public abstract class AbstractExpression {
// 固定返回 int
public abstract int interpreter();
}
B. TerminalExoression 類：NumberExpression 代表了終端，也就是一般數字 (數字無法向下推導)
// TerminalExoression 類
public class NumberExpression extends AbstractExpression {
private final int num;
public NumberExpression(int num) {
this.num = num;
}
@Override
public int interpreter() {
return num;
}
}
C. NonTerminalExoression 類：再次定一個抽象，內部聚合了 AbstractExoression 抽象
// NonTerminalExoression 類
public abstract class OperatorExpression extends AbstractExpression {
protected final AbstractExpression a1;
protected final AbstractExpression a2;
public OperatorExpression(AbstractExpression a1, AbstractExpression a2) {
this.a1 = a1;
this.a2 = a2;
}
}
● 透過繼承 OperatorExpression 來完成不同符號操作
// 加法
public class AddExpression extends OperatorExpression {
public AddExpression(AbstractExpression a1, AbstractExpression a2) {
super(a1, a2);
}
@Override
public int interpreter() {
// 加法操作
return a1.interpreter() + a2.interpreter();
}
}
// ----------------------------------------------------------
// 減法
public class ReduceExpression extends OperatorExpression {
public ReduceExpression(AbstractExpression a1, AbstractExpression a2) {
super(a1, a2);
}
@Override
public int interpreter() {
// 減法操作
return a1.interpreter() - a2.interpreter();
}
}
● OperatorExpression 類設計，方便於拓展操作符號
● 加減 interpreter 實現 UML
套用 Stack 計算
● 這裡使用 Stack 數據結構的特性 (先進後出)，並使用 interpreter 設定做為 Stack element，來運算加減法
這裡規範使用
空格來區隔每個符號
public class Calculation {
private final Stack<AbstractExpression> stack = new Stack<>();
public Calculation(String expression) {
initExpression(expression.split(" "));
}
private void initExpression(String[] symbols) {
for (int i = 0; i < symbols.length; i++) {
String symbol = symbols[i];
switch (symbol) {
// 非終端
case "+":
stack.push(
new AddExpression(
stack.pop(),
new NumberExpression(Integer.parseInt(symbols[++i]))
)
);
break;
// 非終端
case "-":
// 減號
stack.push(
new ReduceExpression(
stack.pop(),
new NumberExpression(Integer.parseInt(symbols[++i]))
)
);
break;
default:
// 一般數字（終端）
stack.push(new NumberExpression(Integer.parseInt(symbol)));
break;
}
}
}
public int getResult() {
return stack.isEmpty() ? -1 : stack.pop().interpreter();
}
}
● User 使用 Calculation 運算加減法 (必須要符合規範)
public class CalMain {
public static void main(String[] args) {
Calculation calculation = new Calculation("1 + 2 + 3 + 5 - 10");
System.out.println("Calculation result: " + calculation.getResult());
}
}
--實做--
Android Source PackageManagerService
Interpreter 的實踐比較少，我們可以在 Android PackageManagerService 解析 APK 時看到類似概念；
在 Android APK 解析 AndroidManifest 文件時會從 application 標籤到 四大組件 or 最外圍的 Perssion... 等等來解析
每個階段都是重複相同的行為 (解析)，但實作又不同，這個概念就是 interpreter
● AndroidManifest.xml 文件
APK 的 AndroidManifest.xml 就相當於一個 APK 的目錄，該 APK 有哪些功能都記錄在該文件上
PakageParser2 開始解析 APK File
● 這邊我們跳過 PackageManagerService 掃描、安裝 APK 的階段 (請看以下簡單流程圖)，直接從 Parser APK 這個文件開始看
● PackageParser2 類：parsePackage 方法負責解析 APK File
// PakageParser2.java
// 解析包的工具類
private ParsingPackageUtils parsingUtils;
// 線程隔離的 ParseTypeImpl
private ThreadLocal<ParseTypeImpl> mSharedResult;
public PackageParser2(String[] separateProcesses, boolean onlyCoreApps,
DisplayMetrics displayMetrics, @Nullable File cacheDir, @NonNull Callback callback) {
... 省略部分
parsingUtils = new ParsingPackageUtils(onlyCoreApps, separateProcesses, displayMetrics,
splitPermissions, callback);
...
}
@AnyThread
public ParsedPackage parsePackage(File packageFile, int flags, boolean useCaches)
throws PackageParserException {
... 省略部分
ParseInput input = mSharedResult.get().reset();
// @ 追蹤 parsePackage 方法
ParseResult<ParsingPackage> result = parsingUtils.parsePackage(input, packageFile, flags);
// 錯誤則直接拋出
if (result.isError()) {
throw new PackageParserException(result.getErrorCode(), result.getErrorMessage(),
result.getException());
}
// 取得解析結果
ParsedPackage parsed = (ParsedPackage) result.getResult().hideAsParsed();
...
return parsed;
}
解析類 - 關係圖
ParsingPackageUtils 解析工具
● ParsingPackageUtils#parsePackage：負責解析檔案 (包括資料夾) 的 APK 檔案
| 解析方法 | 功能 |
|---|---|
| parseClusterPackage | 解析整個資料夾，最終會調用到 parseMonolithicPackage |
| parseMonolithicPackage | 解析單個 Flie |
// ParsingPackageUtils.java
public ParseResult<ParsingPackage> parsePackage(ParseInput input, File packageFile,
int flags)
throws PackageParserException {
// 判斷文件是否是資料夾
if (packageFile.isDirectory()) {
// 最終都會回調到 parseMonolithicPackage 方法
return parseClusterPackage(input, packageFile, flags);
} else {
// @ 追蹤 parseMonolithicPackage 方法
return parseMonolithicPackage(input, packageFile, flags);
}
}
● ParsingPackageUtils#parseMonolithicPackage：解析單個檔案，在這裡會輕量級解析 APK 文件，最後在呼叫parseBaseApk 方法
// ParsingPackageUtils.java
private ParseResult<ParsingPackage> parseMonolithicPackage(ParseInput input, File apkFile,
int flags) throws PackageParserException {
// 輕量級解析
final ParseResult<PackageLite> liteResult =
ApkLiteParseUtils.parseMonolithicPackageLite(input, apkFile, flags);
if (liteResult.isError()) {
return input.error(liteResult);
}
final PackageLite lite = liteResult.getResult();
... 省略失敗
final SplitAssetLoader assetLoader = new DefaultSplitAssetLoader(lite, flags);
try {
// @ 追蹤 parseBaseApk 方法
final ParseResult<ParsingPackage> result = parseBaseApk(input,
apkFile,
apkFile.getCanonicalPath(),
assetLoader, flags);
if (result.isError()) {
return input.error(result);
}
return input.success(result.getResult()
.setUse32BitAbi(lite.isUse32bitAbi()));
} /* 省略 catch、finally */
}
● 當找到要分析的目標 APK 後，就會調用 ParsingPackageUtils#parseBaseApk 方法
A. 如果 baseApk 絕對路徑是以 /mnt/expand/ 開頭，就取 /mnt/expand/ 後的設定為 volumeUuid
B. 透過 AssetManager 解析 baseApk 中的 AndroidManifest.xml 文件
// ParsingPackageUtils.java
public static final String MNT_EXPAND = "/mnt/expand/";
public static final String ANDROID_MANIFEST_FILENAME = "AndroidManifest.xml";
private ParseResult<ParsingPackage> parseBaseApk(ParseInput input, File apkFile,
String codePath, SplitAssetLoader assetLoader, int flags)
throws PackageParserException {
// 取得 baseApk 絕對位置
final String apkPath = apkFile.getAbsolutePath();
// 1. 取得 volumeUuid
String volumeUuid = null;
if (apkPath.startsWith(MNT_EXPAND)) {
final int end = apkPath.indexOf('/', MNT_EXPAND.length());
volumeUuid = apkPath.substring(MNT_EXPAND.length(), end);
}
... log 訊息
// 取得 AssetManager
final AssetManager assets = assetLoader.getBaseAssetManager();
final int cookie = assets.findCookieForPath(apkPath);
if (cookie == 0) {
return input.error(INSTALL_PARSE_FAILED_BAD_MANIFEST,
"Failed adding asset path: " + apkPath);
}
// 2. 指定分析 AndroidManifest.xml 文件
try (XmlResourceParser parser = assets.openXmlResourceParser(cookie,
ANDROID_MANIFEST_FILENAME)) {
final Resources res = new Resources(assets, mDisplayMetrics, null);
// 3. @ 分析 parseBaseApk
ParseResult<ParsingPackage> result = parseBaseApk(input, apkPath, codePath, res,
parser, flags);
... 省略部分
// 用於以後標示這個解析後的 Package
pkg.setVolumeUuid(volumeUuid);
...
return input.success(pkg);
} /* 省略 catch */
}
C. 呼叫重載方法 ParsingPackageUtils#parseBaseApk
● 讀取 attrs_manifest.xml 內的屬性集
● 透過 parseBaseApkTags 方法分析 AndroidManifest 基本屬性
// ParsingPackageUtils.java
// ParseResult 方法重載
private ParseResult<ParsingPackage> parseBaseApk(ParseInput input, String apkPath,
String codePath, Resources res, XmlResourceParser parser, int flags)
throws XmlPullParserException, IOException {
... 省略部分
// 屬性集在 attrs_manifest.xml
final TypedArray manifestArray = res.obtainAttributes(parser, R.styleable.AndroidManifest);
try {
final boolean isCoreApp =
parser.getAttributeBooleanValue(null, "coreApp", false);
final ParsingPackage pkg = mCallback.startParsingPackage(
pkgName, apkPath, codePath, manifestArray, isCoreApp);
// @ 分析 parseBaseApkTags
final ParseResult<ParsingPackage> result =
parseBaseApkTags(input, pkg, manifestArray, res, parser, flags);
if (result.isError()) {
return result;
}
return input.success(pkg);
} finally {
// TypedArray 必須回收
manifestArray.recycle();
}
}
解析 AndroidManifest：Application 標籤
● ParsingPackageUtils#parseBaseApkTags：主要就是讀取 AndroidManifest 資源檔案，並進行解析
// ParsingPackageUtils.java
private ParseResult<ParsingPackage> parseBaseApkTags(ParseInput input, ParsingPackage pkg,
TypedArray sa, Resources res, XmlResourceParser parser, int flags)
throws XmlPullParserException, IOException {
ParseResult<ParsingPackage> sharedUserResult = parseSharedUser(input, pkg, sa);
... 省略部分
boolean foundApp = false;
final int depth = parser.getDepth();
int type;
while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
&& (type != XmlPullParser.END_TAG
|| parser.getDepth() > depth)) {
if (type != XmlPullParser.START_TAG) {
continue;
}
String tagName = parser.getName();
final ParseResult result;
// application 有特別邏輯，所以需要另外處理
if (TAG_APPLICATION.equals(tagName)) {
if (foundApp) {
... 錯誤，一個應用只能有以個 Application 標籤
} else {
foundApp = true;
result = parseBaseApplication(input, pkg, res, parser, flags);
}
} else {
result = parseBaseApkTag(tagName, input, pkg, res, parser, flags);
}
if (result.isError()) {
return input.error(result);
}
}
... 省略部分
return input.success(pkg);
}
● 以下我們來看看它是如何解析 activity 標籤
// ParsingPackageUtils.java
private ParseResult<ParsingPackage> parseBaseApplication(ParseInput input,
ParsingPackage pkg, Resources res, XmlResourceParser parser, int flags)
throws XmlPullParserException, IOException {
// 包名
final String pkgName = pkg.getPackageName();
// 目標 SDK 版本
int targetSdk = pkg.getTargetSdkVersion();
...
final int depth = parser.getDepth();
int type;
while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
&& (type != XmlPullParser.END_TAG
|| parser.getDepth() > depth)) {
if (type != XmlPullParser.START_TAG) {
continue;
}
final ParseResult result;
String tagName = parser.getName();
boolean isActivity = false;
switch (tagName) {
case "activity":
isActivity = true;
// fall-through
case "receiver":
// 從這裡可以看出 activity、receive 的解析是同一個 function
ParseResult<ParsedActivity> activityResult =
ParsedActivityUtils.parseActivityOrReceiver(mSeparateProcesses, pkg,
res, parser, flags, sUseRoundIcon, input);
if (activityResult.isSuccess()) {
ParsedActivity activity = activityResult.getResult();
if (isActivity) {
hasActivityOrder |= (activity.getOrder() != 0);
pkg.addActivity(activity);
} else {
hasReceiverOrder |= (activity.getOrder() != 0);
pkg.addReceiver(activity);
}
}
result = activityResult;
break;
}
}
ParsingPackageImpl 儲存 Package 訊息
● Android 組件解析關係圖，解析的實作交給 Parsed 實作類 (ParsedActivity、ParsedService... 等等)
● ParsingPackageImpl 類負責儲存 APK 最終分析的結果，其中就包含了 4 大組件、 packageName、versionCode... 等等訊息
A. 每個組件中都含有 xxxInfo 數據、該 Info 才是該組件的數據
Activity 內會有 ActivityInfo
Service 內會有 ServiceInfo
B. 四大組件的標籤內有包含 <intent-filter\>，用來過濾 Intent 訊息，其 Package 結果也會保存在 ParsingPackageImpl 中 （透過 ParsedIntentInfoUtils 類解析）
其實就是保存了 AndroidManifest.xml 的訊息
// ParsingPackageImpl.java
public class ParsingPackageImpl implements ParsingPackage, Parcelable {
private static final String TAG = "PackageImpl";
...
// Package 基本資料
protected int versionCode;
protected int versionCodeMajor;
private int baseRevisionCode;
@Nullable
@DataClass.ParcelWith(ForInternedString.class)
private String versionName;
private int compileSdkVersion;
@Nullable
@DataClass.ParcelWith(ForInternedString.class)
private String compileSdkVersionCodeName;
@NonNull
@DataClass.ParcelWith(ForInternedString.class)
protected String packageName;
@Nullable
@DataClass.ParcelWith(ForInternedString.class)
private String realPackage;
@NonNull
protected String mBaseApkPath;
// 四大組件 + 權限
@NonNull
protected List<ParsedActivity> activities = emptyList();
@NonNull
protected List<ParsedActivity> receivers = emptyList();
@NonNull
protected List<ParsedService> services = emptyList();
@NonNull
protected List<ParsedProvider> providers = emptyList();
@NonNull
private List<ParsedAttribution> attributions = emptyList();
@NonNull
protected List<ParsedPermission> permissions = emptyList();
@NonNull
protected List<ParsedPermissionGroup> permissionGroups = emptyList();
@NonNull
protected List<ParsedInstrumentation> instrumentations = emptyList();
// Intent info 訊息
@NonNull
@DataClass.ParcelWith(ParsedIntentInfo.ListParceler.class)
private List<Pair<String, ParsedIntentInfo>> preferredActivityFilters = emptyList();
@NonNull
private Map<String, ParsedProcess> processes = emptyMap();
... 省略部份
}
● 最終 Parser 完畢的 APK 訊息會同步到 PackageManagerService 中保存
更多的物件導向設計
物件導向的設計基礎如下，如果是初學者或是不熟悉的各位，建議可以從這些基礎開始認識，打好基底才能走個更穩（在學習的時候也需要不斷回頭看）！
創建模式 Creation Patterns
● 創建模式 PK
● 創建模式 - Creation Patterns：
創建模式用於「物件的創建」，它關注於如何更靈活、更有效地創建物件。這些模式可以隱藏創建物件的細節，並提供創建物件的機制，例如單例模式、工廠模式… 等等，詳細解說請點擊以下連結
● Singleton 單例模式 | 解說實現 | Android Framework Context Service
● Abstract Factory 設計模式 | 實現解說 | Android MediaPlayer
● Factory 工廠方法模式 | 解說實現 | Java 集合設計
● Builder 建構者模式 | 實現與解說 | Android Framwrok Dialog 視窗
● Clone 原型模式 | 解說實現 | Android Framework Intent
行為模式 Behavioral Patterns
● 行為模式 PK
● 行為模式 - Behavioral Patterns：
行為模式關注物件之間的「通信」和「職責分配」。它們描述了一系列物件如何協作，以完成特定任務。這些模式專注於改進物件之間的通信，從而提高系統的靈活性。例如，策略模式、觀察者模式… 等等，詳細解說請點擊以下連結
● Stragety 策略模式 | 解說實現 | Android Framework 動畫
● Interpreter 解譯器模式 | 解說實現 | Android Framework PackageManagerService
● Chain 責任鏈模式 | 解說實現 | Android Framework View 事件傳遞
● Specification 規格模式 | 解說實現 | Query 語句實做
● Command 命令、Servant 雇工模式 | 實現與解說 | 物件導向設計
● Memo 備忘錄模式 | 實現與解說 | Android Framwrok Activity 保存
● Visitor 設計模式 | 實現與解說 | 物件導向設計
● Template 設計模式 | 實現與解說 | 物件導向設計
● Mediator 模式設計 | 實現與解說 | 物件導向設計
● Composite 組合模式 | 實現與解說 | 物件導向設計
● Observer 觀察者模式 | JDK Observer | Android Framework Listview
結構模式 Structural Patterns
● 結構模式 PK
● 結構模式 - Structural Patterns：
結構模式專注於「物件之間的組成」，以形成更大的結構。這些模式可以幫助你確保當系統進行擴展或修改時，不會破壞其整體結構。例如，外觀模式、代理模式… 等等，詳細解說請點擊以下連結
● Decorate 裝飾模式 | 解說實現 | 物件導向設計
● Iterator 迭代設計 | 解說實現 | 物件導向設計
