/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.jar /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.jar # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty termination of the given Bare JBC problem could be proven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 191 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 134 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (12) TRUE ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class StupidArray { public static void main(String[] args) { int i = 0; while (true) { i = args.length + 1; args[i] = new String(); } } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class StupidArray { public static void main(String[] args) { int i = 0; while (true) { i = args.length + 1; args[i] = new String(); } } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: StupidArray.main([Ljava/lang/String;)V: Graph of 56 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 1 SCCs. ---------------------------------------- (6) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: StupidArray.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (7) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 29 IRulesP rules: f126_0_main_ArrayLength(EOS(STATIC_126), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) -> f130_0_main_ArrayLength(EOS(STATIC_130), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) :|: i7 >= 0 f130_0_main_ArrayLength(EOS(STATIC_130), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) -> f132_0_main_ConstantStackPush(EOS(STATIC_132), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i7) :|: i7 >= 0 f132_0_main_ConstantStackPush(EOS(STATIC_132), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i7) -> f134_0_main_IntArithmetic(EOS(STATIC_134), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i7, 1) :|: TRUE f134_0_main_IntArithmetic(EOS(STATIC_134), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i7, matching1) -> f137_0_main_Store(EOS(STATIC_137), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i7 + 1) :|: i7 >= 0 && matching1 = 1 f137_0_main_Store(EOS(STATIC_137), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8) -> f139_0_main_Load(EOS(STATIC_139), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8) :|: TRUE f139_0_main_Load(EOS(STATIC_139), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8) -> f141_0_main_Load(EOS(STATIC_141), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(ARRAY(i7))) :|: TRUE f141_0_main_Load(EOS(STATIC_141), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(ARRAY(i7))) -> f142_0_main_New(EOS(STATIC_142), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8) :|: TRUE f142_0_main_New(EOS(STATIC_142), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8) -> f145_0_main_Duplicate(EOS(STATIC_145), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) :|: TRUE f145_0_main_Duplicate(EOS(STATIC_145), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) -> f147_0_main_InvokeMethod(EOS(STATIC_147), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f147_0_main_InvokeMethod(EOS(STATIC_147), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f149_0__init__Load(EOS(STATIC_149), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f149_0__init__Load(EOS(STATIC_149), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f151_0__init__InvokeMethod(EOS(STATIC_151), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f151_0__init__InvokeMethod(EOS(STATIC_151), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f152_0__init__Load(EOS(STATIC_152), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f152_0__init__Load(EOS(STATIC_152), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f154_0__init__ConstantStackPush(EOS(STATIC_154), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f154_0__init__ConstantStackPush(EOS(STATIC_154), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f156_0__init__FieldAccess(EOS(STATIC_156), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f156_0__init__FieldAccess(EOS(STATIC_156), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f159_0__init__Load(EOS(STATIC_159), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f159_0__init__Load(EOS(STATIC_159), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f161_0__init__ConstantStackPush(EOS(STATIC_161), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f161_0__init__ConstantStackPush(EOS(STATIC_161), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f163_0__init__FieldAccess(EOS(STATIC_163), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f163_0__init__FieldAccess(EOS(STATIC_163), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f164_0__init__Load(EOS(STATIC_164), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f164_0__init__Load(EOS(STATIC_164), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f165_0__init__ConstantStackPush(EOS(STATIC_165), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f165_0__init__ConstantStackPush(EOS(STATIC_165), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f166_0__init__ArrayCreate(EOS(STATIC_166), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f166_0__init__ArrayCreate(EOS(STATIC_166), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f168_0__init__FieldAccess(EOS(STATIC_168), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(0))) :|: TRUE && matching1 = 0 f168_0__init__FieldAccess(EOS(STATIC_168), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(matching1))) -> f172_0__init__Return(EOS(STATIC_172), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f172_0__init__Return(EOS(STATIC_172), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) -> f175_0_main_ArrayAccess(EOS(STATIC_175), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) :|: TRUE f175_0_main_ArrayAccess(EOS(STATIC_175), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) -> f178_0_main_ArrayAccess(EOS(STATIC_178), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) :|: TRUE f178_0_main_ArrayAccess(EOS(STATIC_178), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) -> f180_0_main_ArrayAccess(EOS(STATIC_180), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) :|: TRUE f180_0_main_ArrayAccess(EOS(STATIC_180), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7)), i8, java.lang.Object(java.lang.String(EOC))) -> f184_0_main_JMP(EOS(STATIC_184), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) :|: i8 < i7 f184_0_main_JMP(EOS(STATIC_184), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) -> f212_0_main_Load(EOS(STATIC_212), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) :|: TRUE f212_0_main_Load(EOS(STATIC_212), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) -> f119_0_main_Load(EOS(STATIC_119), java.lang.Object(ARRAY(i7)), java.lang.Object(ARRAY(i7))) :|: TRUE f119_0_main_Load(EOS(STATIC_119), java.lang.Object(o9sub), java.lang.Object(o9sub)) -> f126_0_main_ArrayLength(EOS(STATIC_126), java.lang.Object(o9sub), java.lang.Object(o9sub), java.lang.Object(o9sub)) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f126_0_main_ArrayLength(EOS(STATIC_126), java.lang.Object(ARRAY(i7:0)), java.lang.Object(ARRAY(i7:0)), java.lang.Object(ARRAY(i7:0))) -> f126_0_main_ArrayLength(EOS(STATIC_126), java.lang.Object(ARRAY(i7:0)), java.lang.Object(ARRAY(i7:0)), java.lang.Object(ARRAY(i7:0))) :|: i7:0 > -1 && i7:0 + 1 < i7:0 Filtered constant ground arguments: f126_0_main_ArrayLength(x1, x2, x3, x4) -> f126_0_main_ArrayLength(x2, x3, x4) EOS(x1) -> EOS Filtered duplicate arguments: f126_0_main_ArrayLength(x1, x2, x3) -> f126_0_main_ArrayLength(x3) Finished conversion. Obtained 1 rules.P rules: f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) -> f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) :|: i7:0 > -1 && i7:0 + 1 < i7:0 ---------------------------------------- (8) Obligation: Rules: f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) -> f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) :|: i7:0 > -1 && i7:0 + 1 < i7:0 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) -> f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) :|: i7:0 > -1 && i7:0 + 1 < i7:0 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) -> f126_0_main_ArrayLength(java.lang.Object(ARRAY(i7:0)), i7:0) :|: i7:0 > -1 && i7:0 + 1 < i7:0 No arcs! This digraph is fully evaluated! ---------------------------------------- (12) TRUE