"""Bounded analysis of published include-reference JSON; no client/archive reads.

Usage: python analyze-graph.py ui-relationships.json [graph-analysis.json]
Only the supplied JSON is read. No extraction, execution, rendering, or network.
Output ordering is deterministic; dates are inherited from the source record.
"""
import collections
import heapq
import json
from pathlib import Path
import re
import sys

MAX_INPUT_BYTES = 2 * 1024 * 1024
MAX_NODES = 512
MAX_EDGES = 2048
MAX_ROOTS = 32
MATCHED = {'exact', 'case-only'}
STATUSES = MATCHED | {'unmatched', 'ambiguous', 'unsupported', 'outside-scope',
                      'external-not-followed', 'fragment-or-empty'}
SAFE_NAME = re.compile(r'[A-Za-z0-9_./ -]{1,180}')


def valid_name(value):
    return (isinstance(value, str) and SAFE_NAME.fullmatch(value)
            and not value.startswith('/')
            and all(part not in ('', '.', '..') for part in value.split('/')))


def checked(data):
    if not isinstance(data, dict):
        raise ValueError('Input must be a JSON object.')
    if not isinstance(data.get('zipSHA256'), str) or not re.fullmatch(r'[a-f0-9]{64}', data['zipSHA256']):
        raise ValueError('A lowercase SHA-256 reference identifier is required.')
    nodes, edges, roots = (data.get(key) for key in ('nodes', 'edges', 'roots'))
    if not all(isinstance(value, list) for value in (nodes, edges, roots)):
        raise ValueError('Nodes, edges, and roots must be arrays.')
    if len(nodes) > MAX_NODES or len(edges) > MAX_EDGES or len(roots) > MAX_ROOTS:
        raise ValueError('Graph exceeds analysis limits.')
    members = {}
    for node in nodes:
        if not isinstance(node, dict) or not valid_name(node.get('name')):
            raise ValueError('Invalid node identifier.')
        name, size = node['name'], node.get('bytes')
        if name in members:
            raise ValueError('Duplicate node identifier.')
        if type(size) is not int or not 0 <= size <= 2 ** 40:
            raise ValueError('Invalid node byte size.')
        members[name] = size
    normalized = []
    for edge in edges:
        if (not isinstance(edge, dict) or not isinstance(edge.get('source'), str)
                or edge['source'] not in members or not isinstance(edge.get('status'), str)
                or edge['status'] not in STATUSES):
            raise ValueError('Invalid edge source or status.')
        target = edge.get('target')
        if edge['status'] in MATCHED and (not isinstance(target, str) or target not in members):
            raise ValueError('Matched edge target is not a declared node.')
        if target is not None and not valid_name(target):
            raise ValueError('Invalid edge target identifier.')
        normalized.append({'source': edge['source'], 'target': target, 'status': edge['status']})
    labels = {}
    for root in roots:
        if (not isinstance(root, dict) or not isinstance(root.get('rootMember'), str)
                or root['rootMember'] not in members or not valid_name(root.get('root'))):
            raise ValueError('Invalid root identifier.')
        if root['rootMember'] in labels:
            raise ValueError('Duplicate root member.')
        labels[root['rootMember']] = root['root']
    date = data.get('inspectedOn')
    if date is not None and (not isinstance(date, str) or not re.fullmatch(r'\d{4}-\d{2}-\d{2}', date)):
        raise ValueError('Invalid source inspection date.')
    return members, normalized, labels


def distances(start, adjacency, available):
    if start not in available:
        return {}
    result = {start: 0}
    queue = collections.deque([start])
    while queue:
        node = queue.popleft()
        for target in sorted(adjacency[node]):
            if target in available and target not in result:
                result[target] = result[node] + 1
                queue.append(target)
    return result


def weak_components(names, adjacency, reverse):
    unseen, groups = set(names), []
    while unseen:
        start = min(unseen)
        group, pending = set(), [start]
        while pending:
            node = pending.pop()
            if node not in unseen:
                continue
            unseen.remove(node)
            group.add(node)
            pending.extend((adjacency[node] | reverse[node]) & unseen)
        groups.append(sorted(group))
    return sorted(groups, key=lambda group: group[0])


def strong_components(names, adjacency, reverse):
    visited, order = set(), []
    for start in sorted(names):
        pending = [(start, False)]
        while pending:
            node, exiting = pending.pop()
            if exiting:
                order.append(node)
            elif node not in visited:
                visited.add(node)
                pending.append((node, True))
                pending.extend((target, False) for target in sorted(adjacency[node], reverse=True) if target not in visited)
    visited, groups = set(), []
    for start in reversed(order):
        if start in visited:
            continue
        group, pending = set(), [start]
        while pending:
            node = pending.pop()
            if node in visited:
                continue
            visited.add(node)
            group.add(node)
            pending.extend(reverse[node] - visited)
        groups.append(sorted(group))
    return sorted(groups, key=lambda group: group[0])


def analyze(data):
    members, edges, labels = checked(data)
    names = set(members)
    matched = [edge for edge in edges if edge['status'] in MATCHED]
    pairs = {(edge['source'], edge['target']) for edge in matched}
    adjacency = {name: set() for name in names}
    reverse = {name: set() for name in names}
    incoming, outgoing = collections.Counter(), collections.Counter()
    for source, target in pairs:
        adjacency[source].add(target)
        reverse[target].add(source)
    for edge in matched:
        outgoing[edge['source']] += 1
        incoming[edge['target']] += 1
    weak = weak_components(names, adjacency, reverse)
    strong = strong_components(names, adjacency, reverse)
    cyclic = [group for group in strong if len(group) > 1 or group[0] in adjacency[group[0]]]
    indegrees = {name: len(reverse[name]) for name in names}
    ready = [name for name in names if not indegrees[name]]
    heapq.heapify(ready)
    topological = []
    while ready:
        node = heapq.heappop(ready)
        topological.append(node)
        for target in sorted(adjacency[node]):
            indegrees[target] -= 1
            if not indegrees[target]:
                heapq.heappush(ready, target)
    baseline = {root: distances(root, adjacency, names) for root in labels}
    root_rows = []
    for root in sorted(labels):
        reached = baseline[root]
        histogram = collections.Counter(reached.values())
        root_rows.append({'name': root, 'label': labels[root], 'reachableNodes': len(reached),
                          'reachableBytes': sum(members[name] for name in reached),
                          'maxShortestDepth': max(reached.values()),
                          'depthHistogram': {str(depth): histogram[depth] for depth in sorted(histogram)},
                          'containsCycle': any(set(group) <= set(reached) for group in cyclic)})
    omissions = []
    for removed in sorted(names):
        available = names - {removed}
        lost = [edge for edge in matched if removed in (edge['source'], edge['target'])]
        losses = []
        for root in sorted(labels):
            after = distances(root, adjacency, available)
            additional = (set(baseline[root]) - {removed}) - set(after)
            if additional or root == removed:
                losses.append({'root': root, 'rootRemoved': root == removed,
                               'additionalUnreachableNodes': len(additional)})
        omissions.append({'name': removed, 'lostMatchedOccurrences': len(lost),
                          'lostUniquePairs': sum(removed in pair for pair in pairs),
                          'remainingWeakComponents': len(weak_components(available, adjacency, reverse)),
                          'rootReachLosses': losses})
    ranking = sorted(omissions, key=lambda row: (-row['lostMatchedOccurrences'], -row['lostUniquePairs'], row['name']))
    largest = max((row['lostMatchedOccurrences'] for row in omissions), default=0)
    folded = collections.defaultdict(list)
    for name in sorted(names):
        folded[name.casefold()].append(name)
    exact_adjacency = {name: set() for name in names}
    exact_reverse = {name: set() for name in names}
    exact_edges = [edge for edge in matched if edge['status'] == 'exact']
    for edge in exact_edges:
        exact_adjacency[edge['source']].add(edge['target'])
        exact_reverse[edge['target']].add(edge['source'])
    policy_roots = []
    for root in sorted(labels):
        exact_reached = distances(root, exact_adjacency, names)
        policy_roots.append({'name': root, 'label': labels[root],
                             'recordedMatchedReachableNodes': len(baseline[root]),
                             'exactOnlyReachableNodes': len(exact_reached),
                             'lostReachableNodes': len(set(baseline[root]) - set(exact_reached))})
    return {
        'schemaVersion': 1, 'methodVersion': '1.0', 'inputFile': 'ui-relationships.json',
        'referenceZIP_SHA256': data['zipSHA256'], 'inputInspectionDate': data.get('inspectedOn'),
        'scope': 'Derived topology of recorded matched literal includes; no client reads, runtime tests, or complete dependency claims.',
        'limits': {'inputBytes': MAX_INPUT_BYTES, 'nodes': MAX_NODES, 'edgeOccurrences': MAX_EDGES, 'roots': MAX_ROOTS},
        'definitions': {'degree': 'Incoming/outgoing occurrences and distinct neighbor counts are separate.',
                        'depth': 'Breadth-first minimum matched-edge distance from each declared root; root depth is zero.',
                        'omission': 'Remove one vertex and its incident matched occurrences. Additional unreachable counts exclude the removed vertex itself.',
                        'components': 'Weak connectivity ignores edge direction; a cyclic strong component has multiple vertices or a self-loop.',
                        'tiePolicy': 'Retain every omission row; rank descending by lost occurrences, then lost pairs, then identifier.'},
        'summary': {'nodes': len(names), 'edgeOccurrences': len(edges), 'matchedOccurrences': len(matched),
                    'excludedOccurrences': len(edges) - len(matched), 'exactOccurrences': sum(e['status'] == 'exact' for e in matched),
                    'caseOnlyOccurrences': sum(e['status'] == 'case-only' for e in matched),
                    'uniqueDirectedPairs': len(pairs), 'duplicateMatchedOccurrences': len(matched) - len(pairs),
                    'weakComponents': len(weak), 'strongComponents': len(strong), 'cyclicComponents': len(cyclic),
                    'isolatedNodes': sum(not adjacency[name] and not reverse[name] for name in names),
                    'emittingNodes': sum(bool(adjacency[name]) for name in names), 'isDAG': not cyclic,
                    'maxRootShortestDepth': max((row['maxShortestDepth'] for row in root_rows), default=None),
                    'maxOmissionLostOccurrences': largest,
                    'mostAffectedRemovals': sorted(row['name'] for row in omissions if row['lostMatchedOccurrences'] == largest)},
        'degrees': [{'name': name, 'inOccurrences': incoming[name], 'outOccurrences': outgoing[name],
                     'inDistinct': len(reverse[name]), 'outDistinct': len(adjacency[name])} for name in sorted(names)],
        'weakComponents': [{'id': index + 1, 'nodes': group, 'nodeCount': len(group)} for index, group in enumerate(weak)],
        'cyclicComponents': cyclic, 'topologicalOrder': topological if not cyclic else None,
        'roots': root_rows, 'caseOnlyEdges': sorted((edge for edge in matched if edge['status'] == 'case-only'), key=lambda row: (row['source'], row['target'])),
        'caseFoldCollisions': [group for _, group in sorted(folded.items()) if len(group) > 1],
        'casePolicyComparison': {'definition': 'Filter existing edge annotations only; no filesystem or application resolver is tested.',
                                 'exactOnlyOccurrences': len(exact_edges),
                                 'exactOnlyWeakComponents': len(weak_components(names, exact_adjacency, exact_reverse)),
                                 'roots': policy_roots},
        'omissions': omissions,
        'omissionRanking': [{'name': row['name'], 'lostMatchedOccurrences': row['lostMatchedOccurrences'], 'lostUniquePairs': row['lostUniquePairs']} for row in ranking],
        'clientFilesRead': False, 'networkConnections': False, 'runtimeExperiments': False,
    }


def render(data):
    return (json.dumps(analyze(data), indent=2, ensure_ascii=True, allow_nan=False) + '\n').encode('ascii')


def main():
    if len(sys.argv) not in (2, 3):
        raise ValueError('Usage: python analyze-graph.py INPUT.json [OUTPUT.json]')
    with open(sys.argv[1], 'rb') as stream:
        content = stream.read(MAX_INPUT_BYTES + 1)
    if len(content) > MAX_INPUT_BYTES:
        raise ValueError('Input exceeds byte limit.')
    data = json.loads(content, parse_constant=lambda _: (_ for _ in ()).throw(ValueError('Non-finite JSON number.')))
    output = render(data)
    if len(sys.argv) == 3:
        Path(sys.argv[2]).write_bytes(output)
    else:
        sys.stdout.buffer.write(output)


if __name__ == '__main__':
    try:
        main()
    except (ValueError, OSError, TypeError, KeyError, RecursionError) as error:
        raise SystemExit('Graph analysis failed: invalid, unreadable, or oversized input.') from None