idlize

1
/*
2
 * Copyright (c) 2024 Huawei Device Co., Ltd.
3
 * Licensed under the Apache License, Version 2.0 (the "License");
4
 * you may not use this file except in compliance with the License.
5
 * You may obtain a copy of the License at
6
 *
7
 * http://www.apache.org/licenses/LICENSE-2.0
8
 *
9
 * Unless required by applicable law or agreed to in writing, software
10
 * distributed under the License is distributed on an "AS IS" BASIS,
11
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
 * See the License for the specific language governing permissions and
13
 * limitations under the License.
14
 */
15

16
import { DeclarationTable, DeclarationTarget, PointerType } from "./DeclarationTable";
17

18
export class DependencySorter {
19
    deps = new Set<DeclarationTarget>()
20

21
    constructor(private table: DeclarationTable) {
22
    }
23

24
    private fillDepsInDepth(target: DeclarationTarget, seen: Set<DeclarationTarget>) {
25
        if (seen.has(target)) return
26
        seen.add(target)
27
        // Need to request that declaration.
28
        this.deps.add(target)
29
        let struct = this.table.targetStruct(target)
30
        struct.supers.forEach(it => this.fillDepsInDepth(it, seen))
31
        struct.getFields().forEach(it => this.fillDepsInDepth(it.declaration, seen))
32
        struct.deps.forEach(dep => this.fillDepsInDepth(dep, seen))
33
        if (target instanceof PointerType)
34
            this.fillDepsInDepth(target.pointed, seen)
35
    }
36

37
    private getDeps(target: DeclarationTarget): DeclarationTarget[] {
38
        let result: DeclarationTarget[] = []
39
        let struct = this.table.targetStruct(target)
40
        struct.supers.forEach(it => result.push(it))
41
        struct.getFields().forEach(it => {
42
            result.push(it.declaration)
43
        })
44
        struct.deps.forEach(it => result.push(it))
45
        return result
46
    }
47

48
    addDep(declaration: DeclarationTarget) {
49
        let seen = new Set<DeclarationTarget>()
50
        this.deps.add(declaration)
51
        this.fillDepsInDepth(declaration, seen)
52
        // if (seen.size > 0) console.log(`${name}: depends on ${Array.from(seen.keys()).join(",")}`)
53
    }
54

55
    // Kahn's algorithm.
56
    getToposorted(): DeclarationTarget[] {
57
        let result: DeclarationTarget[] = []
58
        let input = Array.from(this.deps)
59
        let adjMap = new Map<DeclarationTarget, DeclarationTarget[]>()
60
        for (let key of input) {
61
            adjMap.set(key, this.getDeps(key))
62
        }
63
        let count = 0
64
        // Build adj map.
65
        let inDegree = new Map<DeclarationTarget, number>()
66
        for (let k of input) {
67
            let array: DeclarationTarget[] = []
68
            inDegree.set(k, 0)
69
            adjMap.get(k)?.forEach(it => {
70
                array.push(it)
71
            })
72
            count++
73
        }
74
        // Compute in-degrees.
75
        for (let k of input) {
76
            for (let it of adjMap.get(k)!) {
77
                let old = inDegree.get(it)
78
                if (old == undefined) {
79
                    // throw new Error(`Forgotten type: ${it} of ${k}`)
80
                    old = 0
81
                }
82
                inDegree.set(it, old + 1)
83
            }
84
        }
85
        let queue: DeclarationTarget[] = []
86
        // Insert elements with in-degree 0
87
        for (let k of input) {
88
            if (inDegree.get(k)! == 0) {
89
                queue.push(k)
90
            }
91
        }
92
        // Add all elements with 0
93
        while (queue.length > 0) {
94
            let e = queue.shift()!
95
            result.unshift(e)
96
            let kids = adjMap.get(e)
97
            if (kids != undefined) {
98
                for (let it of kids) {
99
                    let old = inDegree.get(it)! - 1
100
                    inDegree.set(it, old)
101
                    if (old == 0) {
102
                        queue.push(it)
103
                    }
104
                }
105
            }
106
        }
107

108
        if (result.length < input.length) {
109
            let cycle = []
110
            for (let it of input) {
111
                if (!result.includes(it)) {
112
                    cycle.push(it)
113
                }
114
            }
115
            console.log(`CYCLE:\n${cycle.map(it => `${this.table.computeTargetName(it, false)}: ${adjMap.get(it)?.map(it => this.table.computeTargetName(it, false)).join(",")}`).join("\n")}`)
116
            throw new Error("cycle detected")
117
        }
118
        // console.log("DEPS", result.map(it => this.table.computeTargetName(it, false)).join(","))
119
        return result
120
    }
121
}