Source code for onlinejudge_template.analyzer.typing

the module to infer types of variables in format trees

この module はフォーマット木の中に自由に出現する変数の型を推論します。


        loop(counter="i", size="N", sequence([
            item("A", indices="i"),

のようなフォーマット木 (:any:`FormatNode`) と



        "N": int,
        "A": str,


from logging import getLogger
from typing import *

from onlinejudge_template.analyzer.match import match_format
from onlinejudge_template.types import *

logger = getLogger(__name__)

[docs]class TypingError(AnalyzerError): pass
[docs]def get_var_type(value: Union[int, float, str]) -> VarType: if isinstance(value, int): return VarType.ValueInt elif isinstance(value, float): return VarType.Float elif isinstance(value, str): if len(value) == 1: return VarType.Char else: return VarType.String else: assert False
[docs]def unify_types(t1: VarType, t2: VarType) -> VarType: if t1 == t2: return t1 if t1 == VarType.String or t2 == VarType.String: return VarType.String if t1 == VarType.Char or t2 == VarType.Char: return VarType.String if set([t1, t2]) == set([VarType.IndexInt, VarType.ValueInt]): return VarType.ValueInt if set([t1, t2]) == set([VarType.IndexInt, VarType.Float]): return VarType.Float if set([t1, t2]) == set([VarType.ValueInt, VarType.Float]): return VarType.Float assert False
[docs]def get_var_types_from_match_result(values: Dict[VarName, Dict[Tuple[int, ...], Union[int, float, str]]], *, variables: Dict[VarName, VarDecl]) -> Dict[VarName, VarType]: """ :raises TypingError: """ types: Dict[VarName, VarType] = {} for name in variables.keys(): ts = set(map(get_var_type, values[name].values())) while len(ts) >= 2: t1 = ts.pop() t2 = ts.pop() t3 = unify_types(t1, t2) ts.add(t3) if not ts: raise TypingError(f"""failed to infer type: {name} has no candidate types""") types[name] = ts.pop() for decl in variables.values(): for name in decl.depending: if types[name] not in (VarType.IndexInt, VarType.ValueInt): raise TypingError(f"""failed to infer type: {name} used as indices but the type is not an integer""") types[name] = VarType.IndexInt for name, decl in variables.items(): if decl.type is not None: t = unify_types(types[name], decl.type) types[name] = t return types
[docs]def unify_var_types(t1: Dict[VarName, VarType], t2: Dict[VarName, VarType]) -> Dict[VarName, VarType]: assert set(t1.keys()) == set(t2.keys()) t3: Dict[VarName, VarType] = {} for name in t1.keys(): t = unify_types(t1[name], t2[name]) t3[name] = t return t3
[docs]def infer_types_from_instances(node: FormatNode, *, variables: Dict[VarName, VarDecl], instances: List[str]) -> Dict[VarName, VarType]: """ :raises FormatMatchError: :raises TypingError: """ assert instances types: Optional[Dict[VarName, VarType]] = None for i, data in enumerate(instances): values = match_format(node, data, variables=variables) logger.debug("match result for %d-th data: %s", i, values) types2 = get_var_types_from_match_result(values, variables=variables) if types is None: types = types2 else: types = unify_var_types(types, types2) assert types is not None logger.debug("infered types: %s", types) return types
[docs]def update_variables_with_types(*, variables: Dict[VarName, VarDecl], types: Dict[VarName, VarType]) -> Dict[VarName, VarDecl]: """ :raises TypingError: """ updated: Dict[VarName, VarDecl] = {} for name, decl in variables.items(): if decl.type is None: t = types[name] else: t1 = unify_types(types[name], decl.type) t = t1 updated[name] = VarDecl( type=t,, dims=decl.dims, bases=decl.bases, depending=decl.depending, ) return updated