這裡主要介紹一下檢查迴圈定義的結構體、聯合體。是對成員中包含自己本身的結構體、聯合體進行檢查。所謂“成員中包含自己本身”，舉例來說，就是指下麵這樣的定義。 這裡所說的“成員中包含自己本身”是指直接包含自己本身，通過指針來應用自己本身是沒有問題的。例如剛纔的例子，如果是下麵這樣的話就沒有問題了。 剛纔 ...
這裡主要介紹一下檢查迴圈定義的結構體、聯合體。是對成員中包含自己本身的結構體、聯合體進行檢查。所謂“成員中包含自己本身”，舉例來說，就是指下麵這樣的定義。
struct point {
struct point p;
};
這裡所說的“成員中包含自己本身”是指直接包含自己本身，通過指針來應用自己本身是沒有問題的。例如剛纔的例子，如果是下麵這樣的話就沒有問題了。
struct point {
struct point *ptr;
};
剛纔的例子中存在直接的迴圈定義，因此一眼就能看出來。還有如下所示的間接迴圈定義的情況，也需要註意。
struct point_x {
struct point_y y;
};
typedef struct point_x my_point_x;
struct point_y {
my_point_x x;
};
上述例子中還夾雜著使用typedef 定義的類型，因此調查起來更為繁瑣。
檢查“迴圈定義的類型”的方法。進行這樣的類型檢查需要將類型定義的整體當作圖（graph）來思考。
將類型的定義抽象為圖時，可以將類型作為節點，將該類型對其他類型的引用作為邊。例如結構體的定義，將該結構體的類型作為節點，向成員的類型的節點連接一條邊。使用typedef 的情況下，將新定義的類型作為節點，向原來的類型節點引一條邊。
再來看一個例子。現在假設有如下所示的定義。
struct st {
struct point pnt;
long len;
};
typedef unsigned int uint;
struct point {
uint x;
uint y;
};
將上述定義轉化為圖，如圖10.2 所示。
如果發生迴圈定義，那麼在生成類型定義的圖時，圖中某處必定存在閉環。迴圈定義情況下的圖如圖10.3 所示。
可見圖中存在閉環。檢查是否存在迴圈定義，只需檢查類型定義的圖中是否存在閉環即可。
檢測有向圖中的閉環的演算法
因為邊存在方向性，所以類型定義的圖屬於有向圖。要檢測有向圖中是否存在閉環，可以使用如下演算法。
1. 選擇任意一個節點（類型）並標註為“查找中”
2. 沿著邊依次訪問所有與該節點相鄰的節點
3. 如果訪問到的節點沒有標註任何狀態，則將該節點標註為“查找中”；如果標註了“查找結束”，則不做任何處理，返回之前的節點；如果已經標註為“查找中”，則說明存在閉環
4. 從當前的節點重覆步驟2 和3，如果已經沒有可訪問的相鄰節點，則將該節點標註為“查找結束”，並沿原路返回
5. 按照上述流程對所有節點進行處理，如果查找過程中沒有遇到“查找中”狀態的節點，就說明不存在閉環
上述演算法中使用了“有向圖的深度優先檢索”來檢測閉環。簡單地說，該演算法的概要就是“只要節點有未訪問的相鄰節點就試著訪問，調查是否會回到原來的節點”。從演算法執行過程中的某一時刻來看，就是在為從起始節點到某一節點的路徑上的所有節點標註上“查找中”的狀態。
具體演算法如下：
protected void checkRecursiveDefinition(Type t, ErrorHandler h) {
_checkRecursiveDefinition(t, new HashMap<Type, Object>(), h);
}
static final protected Object checking = new Object();
static final protected Object checked = new Object();
/*結構體、聯合體的迴圈定義檢查
* 結構體、聯合體、數組、typedef 所定義的類型以外的類型只有整數類型和指針，因此除
了上述4 個類型以外，其他情況下都不可能出現邊。包含某類型的指針的情況下，因為不會產
生迴圈依賴，所以不會有問題。
演算法說明中的“標註狀態”的實現方式是“將Type 對象和它的狀態作為一組保存在
Map 對象marks 中”，這是上述演算法的重點。
*/
protected void _checkRecursiveDefinition(Type t,
Map<Type, Object> marks,
ErrorHandler h) {
/*
* 如果t 的狀態為“查找中”，輸出錯誤並return
*/
if (marks.get(t) == checking) {
h.error(((NamedType)t).location(),
"recursive type definition: " + t);
return;
}
/*
* t 的狀態為“查找結束”
*/
else if (marks.get(t) == checked) {
return;
}
/*
* 訪問的節點還沒有被標註狀態。
* 將t 標註為“查找中”，
* 訪問所有和t 相鄰的節點（調用_checkRecursiveDefinition），
* 將t 標註為“查找結束”。
*/
else {
marks.put(t, checking);
if (t instanceof CompositeType) {
CompositeType ct = (CompositeType)t;
for (Slot s : ct.members()) {
_checkRecursiveDefinition(s.type(), marks, h);
}
}
else if (t instanceof ArrayType) {
ArrayType at = (ArrayType)t;
_checkRecursiveDefinition(at.baseType(), marks, h);
}
else if (t instanceof UserType) {
UserType ut = (UserType)t;
_checkRecursiveDefinition(ut.realType(), marks, h);
}
marks.put(t, checked);
}
}
