/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 185 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 100 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 5 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: f115_0_main_ArrayLength(EOS(STATIC_115), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f117_0_main_ArrayLength(EOS(STATIC_117), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: i6 >= 0 f117_0_main_ArrayLength(EOS(STATIC_117), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f118_0_main_ConstantStackPush(EOS(STATIC_118), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6) :|: i6 >= 0 f118_0_main_ConstantStackPush(EOS(STATIC_118), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6) -> f120_0_main_IntArithmetic(EOS(STATIC_120), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6, 1) :|: TRUE f120_0_main_IntArithmetic(EOS(STATIC_120), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6, matching1) -> f123_0_main_Store(EOS(STATIC_123), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6 + 1) :|: i6 >= 0 && matching1 = 1 f123_0_main_Store(EOS(STATIC_123), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f125_0_main_Load(EOS(STATIC_125), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) :|: TRUE f125_0_main_Load(EOS(STATIC_125), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f127_0_main_Load(EOS(STATIC_127), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(ARRAY(i6))) :|: TRUE f127_0_main_Load(EOS(STATIC_127), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(ARRAY(i6))) -> f129_0_main_New(EOS(STATIC_129), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) :|: TRUE f129_0_main_New(EOS(STATIC_129), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f132_0_main_Duplicate(EOS(STATIC_132), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE f132_0_main_Duplicate(EOS(STATIC_132), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f134_0_main_InvokeMethod(EOS(STATIC_134), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f134_0_main_InvokeMethod(EOS(STATIC_134), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f136_0__init__Load(EOS(STATIC_136), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f136_0__init__Load(EOS(STATIC_136), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f139_0__init__InvokeMethod(EOS(STATIC_139), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f139_0__init__InvokeMethod(EOS(STATIC_139), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f142_0__init__Load(EOS(STATIC_142), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f142_0__init__Load(EOS(STATIC_142), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f144_0__init__ConstantStackPush(EOS(STATIC_144), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f144_0__init__ConstantStackPush(EOS(STATIC_144), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f146_0__init__FieldAccess(EOS(STATIC_146), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f146_0__init__FieldAccess(EOS(STATIC_146), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f149_0__init__Load(EOS(STATIC_149), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f149_0__init__Load(EOS(STATIC_149), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f151_0__init__ConstantStackPush(EOS(STATIC_151), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, 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__ConstantStackPush(EOS(STATIC_151), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f153_0__init__FieldAccess(EOS(STATIC_153), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f153_0__init__FieldAccess(EOS(STATIC_153), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f155_0__init__Load(EOS(STATIC_155), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f155_0__init__Load(EOS(STATIC_155), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f158_0__init__ConstantStackPush(EOS(STATIC_158), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE f158_0__init__ConstantStackPush(EOS(STATIC_158), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f160_0__init__ArrayCreate(EOS(STATIC_160), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE f160_0__init__ArrayCreate(EOS(STATIC_160), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f163_0__init__FieldAccess(EOS(STATIC_163), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(0))) :|: TRUE && matching1 = 0 f163_0__init__FieldAccess(EOS(STATIC_163), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(matching1))) -> f168_0__init__Return(EOS(STATIC_168), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 f168_0__init__Return(EOS(STATIC_168), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f169_0_main_ArrayAccess(EOS(STATIC_169), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE f169_0_main_ArrayAccess(EOS(STATIC_169), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f170_0_main_ArrayAccess(EOS(STATIC_170), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE f170_0_main_ArrayAccess(EOS(STATIC_170), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f171_0_main_ArrayAccess(EOS(STATIC_171), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE f171_0_main_ArrayAccess(EOS(STATIC_171), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f176_0_main_JMP(EOS(STATIC_176), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: i7 < i6 f176_0_main_JMP(EOS(STATIC_176), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f199_0_main_Load(EOS(STATIC_199), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: TRUE f199_0_main_Load(EOS(STATIC_199), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f112_0_main_Load(EOS(STATIC_112), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: TRUE f112_0_main_Load(EOS(STATIC_112), java.lang.Object(o8sub), java.lang.Object(o8sub)) -> f115_0_main_ArrayLength(EOS(STATIC_115), java.lang.Object(o8sub), java.lang.Object(o8sub), java.lang.Object(o8sub)) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f115_0_main_ArrayLength(EOS(STATIC_115), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0))) -> f115_0_main_ArrayLength(EOS(STATIC_115), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0))) :|: i6:0 > -1 && i6:0 + 1 < i6:0 Filtered constant ground arguments: f115_0_main_ArrayLength(x1, x2, x3, x4) -> f115_0_main_ArrayLength(x2, x3, x4) EOS(x1) -> EOS Filtered duplicate arguments: f115_0_main_ArrayLength(x1, x2, x3) -> f115_0_main_ArrayLength(x3) Finished conversion. Obtained 1 rules.P rules: f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 ---------------------------------------- (8) Obligation: Rules: f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f115_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 No arcs! This digraph is fully evaluated! ---------------------------------------- (12) TRUE