300 lines
16 KiB
Plaintext
300 lines
16 KiB
Plaintext
from stdint import *
|
|
import string
|
|
import stdlib
|
|
import memhub
|
|
import lib.core.IncludesScanner as IncludesScanner
|
|
import lib.Stub.StubMerger as StubMerger
|
|
import lib.Stub.StubMerger.StubMergerCollect as StubMergerCollect
|
|
import lib.Stub.StubMerger.StubMergerIR as StubMergerIR
|
|
import lib.Stub.StubMerger.StubMergerStore as StubMergerStore
|
|
|
|
import lib.Phase.Phase1.Phase1Scan as Phase1Scan
|
|
import lib.Phase.Phase1 as Phase1
|
|
|
|
# Phase1Topo - topologically sort source files by class inheritance and import dependencies.
|
|
# Functions live in this module (accessed via its prefix); globals go through Phase1._xxx.
|
|
|
|
# _TopoSortFiles - topologically sort files by class inheritance (Kahn).
|
|
# Builds a "file SHA1 -> dependency SHA1 set" map, computes in-degrees (parent-file first), then outputs the order; returns 0 or -1.
|
|
def _TopoSortFiles(mb: memhub.MemBuddy*, result: IncludesScanner.ScanResult*, reachable_set: str, reachable_count: int, use_reachable: int, sha1_set: str, set_count: int, class_names_buf: bytes, parent_names_buf: bytes, def_sha1s_buf: bytes, class_count: int, out_order: rawptr, out_count: rawptr, temp_dir: str, td_len_ts: sizet) -> int:
|
|
"""Topologically sort files by class inheritance and import dependencies."""
|
|
if result is None or out_order is None or out_count is None: return -1
|
|
|
|
entry_size: sizet = IncludesScanner.FileEntry.__sizeof__()
|
|
|
|
# 1. Allocate flat arrays: file SHA1, dependency SHA1 list, dep counts, in-degrees, processed flags.
|
|
# Flat arrays replace a FileDepEntry struct to avoid NULL str-pointer fields crashing.
|
|
file_sha1s_buf: bytes = mb.alloc(Phase1.MAX_FILE_DEPS * Phase1.SHA1_LEN)
|
|
# 取消整数提升后，模块属性 CDefine(Phase1.MAX_*) 按最小位宽物化为 i16/i8；三段乘积 256*16*17=69632 会在 i16 回绕，
|
|
# 首乘数显式 sizet() 加宽到 64 位。上一行 256*17=4352 未超 i16，故无需改。
|
|
file_deps_buf: bytes = mb.alloc(sizet(Phase1.MAX_FILE_DEPS) * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN)
|
|
file_dep_counts: rawptr = mb.alloc(Phase1.MAX_FILE_DEPS * 4)
|
|
file_indegrees: rawptr = mb.alloc(Phase1.MAX_FILE_DEPS * 4)
|
|
file_processed: rawptr = mb.alloc(Phase1.MAX_FILE_DEPS * 4)
|
|
|
|
if file_sha1s_buf is None or file_deps_buf is None or file_dep_counts is None or file_indegrees is None or file_processed is None:
|
|
if file_sha1s_buf is not None: mb.free(file_sha1s_buf)
|
|
if file_deps_buf is not None: mb.free(file_deps_buf)
|
|
if file_dep_counts is not None: mb.free(file_dep_counts)
|
|
if file_indegrees is not None: mb.free(file_indegrees)
|
|
if file_processed is not None: mb.free(file_processed)
|
|
return -1
|
|
|
|
string.memset(file_sha1s_buf, 0, Phase1.MAX_FILE_DEPS * Phase1.SHA1_LEN)
|
|
string.memset(file_deps_buf, 0, sizet(Phase1.MAX_FILE_DEPS) * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN)
|
|
string.memset(file_dep_counts, 0, Phase1.MAX_FILE_DEPS * 4)
|
|
string.memset(file_indegrees, 0, Phase1.MAX_FILE_DEPS * 4)
|
|
string.memset(file_processed, 0, Phase1.MAX_FILE_DEPS * 4)
|
|
|
|
file_count: int = 0
|
|
# sha1 -> file_index map (simple linear search; file count is small)
|
|
for i in range(int(result.Count)):
|
|
entry_addr: uint64 = uint64(result.Entries) + i * entry_size
|
|
entry: IncludesScanner.FileEntry* = IncludesScanner.FileEntry*(entry_addr)
|
|
if entry is None or entry.Sha1 is None: continue
|
|
|
|
sha1_e: str = entry.Sha1
|
|
in_set: int = 0
|
|
if use_reachable != 0: in_set = StubMergerCollect._is_in_sha1_set(sha1_e, reachable_set, reachable_count)
|
|
else: in_set = StubMergerCollect._is_in_sha1_set(sha1_e, sha1_set, set_count)
|
|
if in_set == 0: continue
|
|
|
|
if file_count >= Phase1.MAX_FILE_DEPS: break
|
|
|
|
# Initialize the flat array: file SHA1 (offset = file_count * Phase1.SHA1_LEN).
|
|
# DepCount/InDegree/Processed are already zeroed by memset.
|
|
sha1_dst: str = file_sha1s_buf + file_count * Phase1.SHA1_LEN
|
|
string.strcpy(sha1_dst, sha1_e)
|
|
|
|
file_count += 1
|
|
|
|
# 2. Build dependency edges: for each class, find the parent's defining file and add a child->parent edge
|
|
for ci in range(int(class_count)):
|
|
# Read parent class name (offset = ci * Phase1.CLASS_NAME_LEN)
|
|
parent_ptr: str = parent_names_buf + ci * Phase1.CLASS_NAME_LEN
|
|
if parent_ptr[0] == '\0': continue
|
|
|
|
# Read child class definition SHA1 (offset = ci * Phase1.SHA1_LEN)
|
|
child_def_sha1: str = def_sha1s_buf + ci * Phase1.SHA1_LEN
|
|
|
|
# Find the SHA1 of the file defining the parent class
|
|
parent_sha1: str = Phase1Scan._FindClassDefSha1(class_names_buf, def_sha1s_buf, class_count, parent_ptr)
|
|
if parent_sha1 is None:
|
|
continue # parent not in includes (e.g. Object, CEnum marker base classes)
|
|
|
|
# The parent file SHA1 must differ from the child's (same-file inheritance needs no dependency)
|
|
if string.strcmp(parent_sha1, child_def_sha1) == 0: continue
|
|
|
|
# Find the child file's index and add the parent file SHA1 to its dependency list
|
|
for fi in range(int(file_count)):
|
|
fsha1: str = file_sha1s_buf + fi * Phase1.SHA1_LEN
|
|
if string.strcmp(fsha1, child_def_sha1) != 0: continue
|
|
|
|
# Read the current dependency count
|
|
cnt_addr: uint64 = uint64(file_dep_counts) + fi * 4
|
|
cnt_ptr: int* = (int*)(cnt_addr)
|
|
if cnt_ptr is None: break
|
|
cur_cnt: int = cnt_ptr[0]
|
|
|
|
# Check whether the dependency is already present (dedupe)
|
|
already: int = 0
|
|
for di in range(int(cur_cnt)):
|
|
dep_slot: str = file_deps_buf + fi * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + di * Phase1.SHA1_LEN
|
|
if string.strcmp(dep_slot, parent_sha1) == 0:
|
|
already = 1
|
|
break
|
|
if already != 0: break
|
|
|
|
if cur_cnt < Phase1.MAX_DEP_EDGES:
|
|
dep_dst: str = file_deps_buf + fi * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + cur_cnt * Phase1.SHA1_LEN
|
|
string.strcpy(dep_dst, parent_sha1)
|
|
cnt_ptr[0] = cur_cnt + 1
|
|
break
|
|
|
|
# 2.5 Add import dependency edges: imported modules must be fully translated first.
|
|
# Class inheritance alone is insufficient (cross-module globals/vtable TypeStr/generics need deps); deps come from Phase 1a-pre, mapped via _BuildIncludesSha1Map.
|
|
sha1_arr_ts: bytes = stdlib.malloc(StubMerger.MAX_INCLUDES * 17)
|
|
mod_arr_ts: bytes = stdlib.malloc(StubMerger.MAX_INCLUDES * 64)
|
|
map_count_ts: int = 0
|
|
if sha1_arr_ts is not None and mod_arr_ts is not None:
|
|
map_count_ts = StubMergerIR._BuildIncludesSha1Map(temp_dir, td_len_ts, sha1_arr_ts, mod_arr_ts)
|
|
for fi_imp in range(int(file_count)):
|
|
if map_count_ts <= 0: break
|
|
fsha1_imp: str = file_sha1s_buf + fi_imp * Phase1.SHA1_LEN
|
|
deps_imp: str = StubMergerStore.LookupIncludesDeps(fsha1_imp)
|
|
if deps_imp is None: continue
|
|
dl_imp: sizet = string.strlen(deps_imp)
|
|
dpos_imp: sizet = 0
|
|
while dpos_imp < dl_imp:
|
|
dstart_imp: sizet = dpos_imp
|
|
while dpos_imp < dl_imp and deps_imp[dpos_imp] != ' ': dpos_imp += 1
|
|
dlen_imp: sizet = dpos_imp - dstart_imp
|
|
if dpos_imp < dl_imp: dpos_imp += 1
|
|
if dlen_imp == 0: continue
|
|
dname_imp: bytes = stdlib.malloc(dlen_imp + 1)
|
|
if dname_imp is None: continue
|
|
string.strncpy(dname_imp, deps_imp + dstart_imp, dlen_imp)
|
|
dname_imp[dlen_imp] = '\0'
|
|
dsha1_imp: str = StubMergerIR._FindSha1ByModName(sha1_arr_ts, mod_arr_ts, map_count_ts, dname_imp)
|
|
stdlib.free(dname_imp)
|
|
if dsha1_imp is None: continue
|
|
# Find the dependency file's index in the list (skip self)
|
|
for fj_imp in range(int(file_count)):
|
|
if string.strcmp(file_sha1s_buf + fj_imp * Phase1.SHA1_LEN, dsha1_imp) != 0: continue
|
|
if fj_imp == fi_imp: break
|
|
# Dedupe and add the edge: fi_imp depends on fj_imp (InDegree[fi_imp]++)
|
|
cnt_addr_imp: uint64 = uint64(file_dep_counts) + fi_imp * 4
|
|
cnt_ptr_imp: int* = (int*)(cnt_addr_imp)
|
|
if cnt_ptr_imp is None: break
|
|
cur_cnt_imp: int = cnt_ptr_imp[0]
|
|
already_imp: int = 0
|
|
for di_imp in range(int(cur_cnt_imp)):
|
|
dep_slot_imp: str = file_deps_buf + fi_imp * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + di_imp * Phase1.SHA1_LEN
|
|
if string.strcmp(dep_slot_imp, dsha1_imp) == 0:
|
|
already_imp = 1
|
|
break
|
|
if already_imp == 0 and cur_cnt_imp < Phase1.MAX_DEP_EDGES:
|
|
dep_dst_imp: str = file_deps_buf + fi_imp * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + cur_cnt_imp * Phase1.SHA1_LEN
|
|
string.strcpy(dep_dst_imp, dsha1_imp)
|
|
cnt_ptr_imp[0] = cur_cnt_imp + 1
|
|
break
|
|
|
|
# Free the local mapping arrays used for import edges
|
|
if sha1_arr_ts is not None: stdlib.free(sha1_arr_ts)
|
|
if mod_arr_ts is not None: stdlib.free(mod_arr_ts)
|
|
|
|
# 3. Kahn: InDegree = DepCount (number of parent files depended on).
|
|
# Process zero-dependency files first, then decrement the in-degree of dependents.
|
|
for fi in range(int(file_count)):
|
|
cnt_addr3: uint64 = uint64(file_dep_counts) + fi * 4
|
|
cnt_ptr3: int* = (int*)(cnt_addr3)
|
|
ind_addr3: uint64 = uint64(file_indegrees) + fi * 4
|
|
ind_ptr3: int* = (int*)(ind_addr3)
|
|
if cnt_ptr3 is not None and ind_ptr3 is not None: ind_ptr3[0] = cnt_ptr3[0]
|
|
|
|
# 4. Topological sort output
|
|
out_idx: int = 0
|
|
changed: int = 1
|
|
while changed != 0:
|
|
changed = 0
|
|
for fi in range(int(file_count)):
|
|
# Check processed flag
|
|
proc_addr4: uint64 = uint64(file_processed) + fi * 4
|
|
proc_ptr4: int* = (int*)(proc_addr4)
|
|
if proc_ptr4 is None or proc_ptr4[0] != 0: continue
|
|
# Check in-degree
|
|
ind_addr4: uint64 = uint64(file_indegrees) + fi * 4
|
|
ind_ptr4: int* = (int*)(ind_addr4)
|
|
if ind_ptr4 is None or ind_ptr4[0] > 0: continue
|
|
|
|
# In-degree 0: can be processed
|
|
# Find the matching result.Entries index
|
|
target_sha1: str = file_sha1s_buf + fi * Phase1.SHA1_LEN
|
|
for ri in range(int(result.Count)):
|
|
ea_r: uint64 = uint64(result.Entries) + ri * entry_size
|
|
ent_r: IncludesScanner.FileEntry* = IncludesScanner.FileEntry*(ea_r)
|
|
if ent_r is not None and ent_r.Sha1 is not None:
|
|
if string.strcmp(ent_r.Sha1, target_sha1) == 0:
|
|
# Write into the output index array
|
|
out_idx_addr: uint64 = uint64(out_order) + out_idx * 4
|
|
out_int_ptr: int* = (int*)(out_idx_addr)
|
|
if out_int_ptr is not None: out_int_ptr[0] = ri
|
|
out_idx += 1
|
|
break
|
|
|
|
# Mark as processed
|
|
proc_ptr4[0] = 1
|
|
changed = 1
|
|
|
|
# Decrement the in-degree of files that depend on this one
|
|
for fj in range(int(file_count)):
|
|
proc_addr5: uint64 = uint64(file_processed) + fj * 4
|
|
proc_ptr5: int* = (int*)(proc_addr5)
|
|
if proc_ptr5 is None or proc_ptr5[0] != 0: continue
|
|
# Read fj's dependency count
|
|
cnt_addr5: uint64 = uint64(file_dep_counts) + fj * 4
|
|
cnt_ptr5: int* = (int*)(cnt_addr5)
|
|
if cnt_ptr5 is None: continue
|
|
fj_dep_cnt: int = cnt_ptr5[0]
|
|
for di in range(int(fj_dep_cnt)):
|
|
dep_slot5: str = file_deps_buf + fj * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + di * Phase1.SHA1_LEN
|
|
if string.strcmp(dep_slot5, target_sha1) == 0:
|
|
ind_addr5: uint64 = uint64(file_indegrees) + fj * 4
|
|
ind_ptr5: int* = (int*)(ind_addr5)
|
|
if ind_ptr5 is not None: ind_ptr5[0] = ind_ptr5[0] - 1
|
|
break
|
|
|
|
# Handle cycles: within a cycle emit the more-depended-upon files first.
|
|
# On-demand container injection (e.g. string -> _list) plus real imports form pseudo-cycles Kahn cannot fully drain; scan order would translate dependents first -> unregistered cross-module vtable TypeStr.
|
|
if out_idx < file_count:
|
|
rem_idx: int* = (int*)(stdlib.malloc(4 * file_count))
|
|
rem_depcnt: int* = (int*)(stdlib.malloc(4 * file_count))
|
|
rem_count: int = 0
|
|
if rem_idx is not None and rem_depcnt is not None:
|
|
for fi in range(int(file_count)):
|
|
proc_addr7: uint64 = uint64(file_processed) + fi * 4
|
|
proc_ptr7: int* = (int*)(proc_addr7)
|
|
if proc_ptr7 is not None and proc_ptr7[0] == 0:
|
|
rem_idx[rem_count] = fi
|
|
rem_depcnt[rem_count] = 0
|
|
rem_count += 1
|
|
# Compute each remaining file's dependents count (among the remaining files)
|
|
for i_a in range(int(rem_count)):
|
|
fi_a: int = rem_idx[i_a]
|
|
target_sha1_a: str = file_sha1s_buf + fi_a * Phase1.SHA1_LEN
|
|
for i_b in range(int(rem_count)):
|
|
fi_b: int = rem_idx[i_b]
|
|
if fi_b == fi_a: continue
|
|
cnt_addr_b: uint64 = uint64(file_dep_counts) + fi_b * 4
|
|
cnt_ptr_b: int* = (int*)(cnt_addr_b)
|
|
if cnt_ptr_b is None: continue
|
|
cnt_b: int = cnt_ptr_b[0]
|
|
for di_b in range(int(cnt_b)):
|
|
dep_slot_b: str = file_deps_buf + fi_b * Phase1.MAX_DEP_EDGES * Phase1.SHA1_LEN + di_b * Phase1.SHA1_LEN
|
|
if string.strcmp(dep_slot_b, target_sha1_a) == 0:
|
|
rem_depcnt[i_a] = rem_depcnt[i_a] + 1
|
|
break
|
|
# Bubble sort descending (more dependents first)
|
|
for i_a in range(int(rem_count)):
|
|
for j_a in range(int(rem_count - 1)):
|
|
if rem_depcnt[j_a] < rem_depcnt[j_a + 1]:
|
|
tmp_i: int = rem_idx[j_a]
|
|
rem_idx[j_a] = rem_idx[j_a + 1]
|
|
rem_idx[j_a + 1] = tmp_i
|
|
tmp_d: int = rem_depcnt[j_a]
|
|
rem_depcnt[j_a] = rem_depcnt[j_a + 1]
|
|
rem_depcnt[j_a + 1] = tmp_d
|
|
# Emit the remaining files in order
|
|
for i_a in range(int(rem_count)):
|
|
fi_a2: int = rem_idx[i_a]
|
|
proc_addr8: uint64 = uint64(file_processed) + fi_a2 * 4
|
|
proc_ptr8: int* = (int*)(proc_addr8)
|
|
if proc_ptr8 is None or proc_ptr8[0] != 0: continue
|
|
target_sha1_2: str = file_sha1s_buf + fi_a2 * Phase1.SHA1_LEN
|
|
for ri in range(int(result.Count)):
|
|
ea_r2: uint64 = uint64(result.Entries) + ri * entry_size
|
|
ent_r2: IncludesScanner.FileEntry* = IncludesScanner.FileEntry*(ea_r2)
|
|
if ent_r2 is not None and ent_r2.Sha1 is not None:
|
|
if string.strcmp(ent_r2.Sha1, target_sha1_2) == 0:
|
|
out_idx_addr2: uint64 = uint64(out_order) + out_idx * 4
|
|
out_int_ptr2: int* = (int*)(out_idx_addr2)
|
|
if out_int_ptr2 is not None: out_int_ptr2[0] = ri
|
|
out_idx += 1
|
|
break
|
|
proc_ptr8[0] = 1
|
|
stdlib.free(rem_idx)
|
|
stdlib.free(rem_depcnt)
|
|
|
|
# Write the output count
|
|
out_count_ptr: int* = (int*)(out_count)
|
|
if out_count_ptr is not None: out_count_ptr[0] = out_idx
|
|
|
|
# Free the flat arrays
|
|
mb.free(file_sha1s_buf)
|
|
mb.free(file_deps_buf)
|
|
mb.free(file_dep_counts)
|
|
mb.free(file_indegrees)
|
|
mb.free(file_processed)
|
|
|
|
return 0
|