1 | package felix.compiler; |
2 | |
3 | import java.util.ArrayList; |
4 | import java.util.HashMap; |
5 | import java.util.HashSet; |
6 | import java.util.Iterator; |
7 | |
8 | import tuffy.mln.Literal; |
9 | import tuffy.mln.Term; |
10 | import tuffy.ra.Expression; |
11 | import tuffy.ra.Function; |
12 | import tuffy.util.ExceptionMan; |
13 | import tuffy.util.StringMan; |
14 | import tuffy.util.Timer; |
15 | |
16 | |
17 | import felix.dstruct.FelixClause; |
18 | import felix.dstruct.FelixPredicate; |
19 | import felix.dstruct.FelixQuery; |
20 | import felix.dstruct.FelixPredicate.FPProperty; |
21 | import felix.dstruct.StatOperator.OPType; |
22 | import felix.parser.FelixCommandOptions; |
23 | |
24 | /** |
25 | * The class of static analyzer that parses a given |
26 | * MLN program. It takes as input |
27 | * the whole MLN program, and assign properties to each |
28 | * predicate. Properties include |
29 | * whether a predicate is SYMM, REFLEX, TRANS etc., or |
30 | * whether a clause specifies a CRF |
31 | * chain etc. |
32 | * |
33 | * @author Ce Zhang |
34 | * |
35 | */ |
36 | public class StaticAnalyzer { |
37 | |
38 | /** |
39 | * Felix Query. |
40 | */ |
41 | FelixQuery fq; |
42 | |
43 | /** |
44 | * Command line options. |
45 | */ |
46 | FelixCommandOptions options; |
47 | |
48 | /** |
49 | * The constructor. |
50 | * @param _fq |
51 | * @param _opt |
52 | */ |
53 | public StaticAnalyzer(FelixQuery _fq, FelixCommandOptions _opt){ |
54 | fq = _fq; |
55 | options = _opt; |
56 | } |
57 | |
58 | |
59 | /** |
60 | * Analyze the input MLN program and assign properties to each predicate. |
61 | */ |
62 | public void parse(){ |
63 | |
64 | //classify clauses and register them to predicates |
65 | //Note: the invocation order matters! |
66 | this.parseKeyConstraintRelation(); |
67 | this.parseReflexiveRelation(); |
68 | this.parseSymmetricRelation(); |
69 | this.parseTransitiveRelation(); |
70 | this.parseChainRecursiveRelation(); |
71 | this.parseNonRecursiveRelation(); |
72 | this.parseOtherRecursiveRelation(); |
73 | this.parseSpecialPredicate(); |
74 | this.parseEmbededWeightRule(); |
75 | //this.parseSymmetricRelationPi2P(); |
76 | } |
77 | |
78 | /** |
79 | * Parse the predicate serves as the linear-representation of COREF. |
80 | */ |
81 | public void parseSpecialPredicate(){ |
82 | |
83 | for(FelixPredicate p : fq.getAllPred()){ |
84 | String name = p.getName(); |
85 | if(name.endsWith("_map")){ |
86 | |
87 | String oriName = name.replaceAll("_map$", ""); |
88 | |
89 | if(fq.getPredByName(oriName) == null){ |
90 | ExceptionMan.die("Cannot use predicate P_map without predicate P, please change to another name."); |
91 | } |
92 | |
93 | FelixPredicate orip = fq.getPredByName(oriName); |
94 | |
95 | if(orip.isClosedWorld()){ |
96 | ExceptionMan.die("Cannot use predicate P with predicate P as closed. Please change P to co-ref predicate, or" + |
97 | " change the name of P_map"); |
98 | } |
99 | |
100 | if(!p.isClosedWorld()){ |
101 | ExceptionMan.die("Cannot use predicate P_map with open-world setting. Plase change P_map to closed-world, or" + |
102 | " change the name of P_map"); |
103 | } |
104 | |
105 | orip.mustbe = OPType.COREF; |
106 | p.oriCorefPredicate = orip; |
107 | p.isCorefMapPredicate = true; |
108 | |
109 | orip.corefMAPPredicate = p; |
110 | |
111 | } |
112 | } |
113 | |
114 | } |
115 | |
116 | /** |
117 | * Parse predicate with key constraints. |
118 | */ |
119 | public void parseKeyConstraintRelation(){ |
120 | |
121 | // get key constraint from predicate declaration |
122 | for(FelixPredicate fp : fq.getAllPred()){ |
123 | if(fp.hasDependentAttributes()){ |
124 | |
125 | Object[] _labelpos = fp.getLabelAttrPositions().toArray(); |
126 | int[] labelpos = new int[_labelpos.length]; |
127 | |
128 | for(int i=0;i<_labelpos.length;i++){ |
129 | labelpos[i] = (Integer) _labelpos[i]; |
130 | } |
131 | |
132 | fp.registerProperty( |
133 | FelixPredicate.FPProperty.KEY_CONSTRAINT, |
134 | null, |
135 | labelpos); |
136 | } |
137 | } |
138 | |
139 | // discover rules like R(a,b1), [b1!=b2], => !R(a,b2) |
140 | for(FelixClause fc : fq.getAllClause()){ |
141 | |
142 | if(fc.getRegLiterals().size() != 2 || |
143 | fc.isHardClause() == false){ |
144 | continue; |
145 | } |
146 | |
147 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
148 | |
149 | for(Literal l : fc.getRegLiterals()){ |
150 | |
151 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
152 | |
153 | if(processedPred.contains(p)){ |
154 | continue; |
155 | } |
156 | |
157 | processedPred.add(p); |
158 | |
159 | if(p.isClosedWorld()){ |
160 | continue; |
161 | } |
162 | |
163 | Literal l1 = fc.getRegLiterals().get(0); |
164 | Literal l2 = fc.getRegLiterals().get(1); |
165 | |
166 | if(fc.getConstraints().size() != 1 || |
167 | l1.getPred().equals(l2.getPred()) == false){ |
168 | continue; |
169 | } |
170 | |
171 | Expression e = fc.getConstraints().get(0); |
172 | String var1 = "", var2 = ""; |
173 | |
174 | boolean eqNeqFlag = false; |
175 | if(e.getFunction() == Function.NOT){ |
176 | e = e.getArgs().get(0); |
177 | eqNeqFlag = true; |
178 | } |
179 | |
180 | if ( ( eqNeqFlag == false && e.getFunction() == Function.Neq ) || |
181 | ( eqNeqFlag == true && e.getFunction() == Function.Eq ) ){ |
182 | |
183 | if(l1.getSense() == true || l2.getSense() == true){ |
184 | continue; |
185 | } |
186 | |
187 | if(e.getArgs().size() != 2){ |
188 | continue; |
189 | } |
190 | |
191 | Expression e1 = e.getArgs().get(0); |
192 | Expression e2 = e.getArgs().get(1); |
193 | |
194 | if(e1.getFunction() != Function.VariableBinding |
195 | || e2.getFunction() != Function.VariableBinding){ |
196 | continue; |
197 | } |
198 | |
199 | var1 = e1.toString(); |
200 | var2 = e2.toString(); |
201 | }else{ |
202 | continue; |
203 | } |
204 | |
205 | //check |
206 | ArrayList<Term> ta = l1.getTerms(); |
207 | ArrayList<Term> tb = l2.getTerms(); |
208 | |
209 | if(ta.size() != tb.size()) continue; |
210 | |
211 | boolean isLR = true; |
212 | boolean isFirst = false; |
213 | int firstI = -1; |
214 | ArrayList<Integer> __labelpos = new ArrayList<Integer>(); |
215 | for(int i=0;i<ta.size();i++){ |
216 | if(ta.get(i).toString().equals(tb.get(i).toString()) == false){ |
217 | |
218 | if( (ta.get(i).toString().equals(var1) && tb.get(i).toString().equals(var2) && isFirst ==false) || |
219 | (tb.get(i).toString().equals(var1) && ta.get(i).toString().equals(var2) && isFirst ==false) ){ |
220 | firstI = i; |
221 | isFirst = true; |
222 | }else{ |
223 | isLR = false; |
224 | } |
225 | |
226 | __labelpos.add(i); |
227 | |
228 | }else{ |
229 | //__keypos.add(i); |
230 | } |
231 | } |
232 | |
233 | if(firstI == -1 || isLR == false){ |
234 | continue; |
235 | } |
236 | |
237 | Object[] _labelpos = __labelpos.toArray(); |
238 | int[] labelpos = new int[_labelpos.length]; |
239 | |
240 | for(int i=0;i<_labelpos.length;i++){ |
241 | labelpos[i] = (Integer) _labelpos[i]; |
242 | } |
243 | |
244 | p.registerProperty( |
245 | FelixPredicate.FPProperty.KEY_CONSTRAINT, |
246 | fc, |
247 | labelpos); |
248 | } |
249 | } |
250 | |
251 | } |
252 | |
253 | /** |
254 | * Generates all permutations of the given terms. |
255 | * @param terms |
256 | * @return |
257 | */ |
258 | public HashSet<ArrayList<String>> generateAllPermutations(HashSet<String> terms){ |
259 | HashSet<ArrayList<String>> ret = new HashSet<ArrayList<String>>(); |
260 | |
261 | if(terms.size() == 1){ |
262 | ArrayList<String> tmp = new ArrayList<String>(); |
263 | tmp.add(terms.iterator().next()); |
264 | ret.add(tmp); |
265 | return ret; |
266 | } |
267 | |
268 | for(String first : terms){ |
269 | |
270 | HashSet<String> newTerms = (HashSet<String>) terms.clone(); |
271 | newTerms.remove(first); |
272 | |
273 | HashSet<ArrayList<String>> others = this.generateAllPermutations(newTerms); |
274 | for(ArrayList<String> a : others){ |
275 | a.add(first); |
276 | ret.add(a); |
277 | } |
278 | } |
279 | |
280 | return ret; |
281 | } |
282 | |
283 | /** |
284 | * Returns true if this set of literals is symmetric. |
285 | * This set of literals decide a conjunctive query: |
286 | * <br/> |
287 | * body => head |
288 | * <br/> |
289 | * |
290 | * For EXP only! |
291 | * |
292 | * @param Head |
293 | * @param body |
294 | * @return |
295 | * @throws CloneNotSupportedException |
296 | */ |
297 | public boolean isSymmetric(Literal Head, HashSet<Literal> body) throws CloneNotSupportedException{ |
298 | |
299 | // first, revert the head variable |
300 | HashSet<String> OriSignatures = new HashSet<String>(); |
301 | HashSet<String> headTerms = new HashSet<String>(); |
302 | HashSet<String> intermediateTerms = new HashSet<String>(); |
303 | |
304 | for(Term t : Head.getTerms()){ |
305 | headTerms.add(t.toString()); |
306 | } |
307 | |
308 | for(Literal l : body){ |
309 | OriSignatures.add(l.toString()); |
310 | for(Term t : l.getTerms()){ |
311 | if(!headTerms.contains(t.toString())){ |
312 | intermediateTerms.add(t.toString()); |
313 | } |
314 | } |
315 | } |
316 | |
317 | String t1 = ""; |
318 | String t2 = ""; |
319 | if(Head.getPred().arity() > 2){ |
320 | t1 = Head.getTerms().get(1).toString(); |
321 | t2 = Head.getTerms().get(2).toString(); |
322 | }else{ |
323 | t1 = Head.getTerms().get(0).toString(); |
324 | t2 = Head.getTerms().get(1).toString(); |
325 | } |
326 | |
327 | HashSet<ArrayList<String>> permutations = |
328 | this.generateAllPermutations(intermediateTerms); |
329 | |
330 | boolean isFinalContained = false; |
331 | if(permutations.size() == 0){ |
332 | boolean isContained = true; |
333 | for(Literal ll : body){ |
334 | |
335 | Literal l = (Literal) ll.clone(); |
336 | |
337 | for(Term t : l.getTerms()){ |
338 | if(t.isConstant()){ |
339 | continue; |
340 | } |
341 | if(t.toString().equals(t1)){ |
342 | t.reSet(t2); |
343 | }else if(t.toString().equals(t2)){ |
344 | t.reSet(t1); |
345 | } |
346 | } |
347 | |
348 | if(!OriSignatures.contains(l.toString())){ |
349 | isContained = false; |
350 | } |
351 | } |
352 | if(isContained == true){ |
353 | isFinalContained = true; |
354 | } |
355 | }else{ |
356 | for(ArrayList<String> maps : permutations){ |
357 | |
358 | HashMap<String, String> map = new HashMap<String, String>(); |
359 | Iterator<String> it = intermediateTerms.iterator(); |
360 | int i=0; |
361 | for(i=0;i<maps.size();i++){ |
362 | map.put(it.next(), maps.get(i)); |
363 | } |
364 | |
365 | boolean isContained = true; |
366 | for(Literal ll : body){ |
367 | |
368 | Literal l = (Literal) ll.clone(); |
369 | |
370 | for(Term t : l.getTerms()){ |
371 | if(t.isConstant()){ |
372 | continue; |
373 | } |
374 | if(t.toString().equals(t1)){ |
375 | t.reSet(t2); |
376 | }else if(t.toString().equals(t2)){ |
377 | t.reSet(t1); |
378 | }else if(!headTerms.contains(t.toString())){ |
379 | t.reSet(map.get(t.toString())); |
380 | } |
381 | } |
382 | |
383 | if(!OriSignatures.contains(l.toString())){ |
384 | isContained = false; |
385 | } |
386 | } |
387 | if(isContained == true){ |
388 | isFinalContained = true; |
389 | } |
390 | } |
391 | } |
392 | return isFinalContained; |
393 | } |
394 | |
395 | /** |
396 | * Parse predicate which is symmetric. |
397 | */ |
398 | public void parseSymmetricRelationPi2P(){ |
399 | |
400 | try { |
401 | |
402 | Timer.start("pi2p"); |
403 | |
404 | // first, generate testing rules |
405 | HashMap<FelixPredicate, HashSet<FelixClause>> testingRules = |
406 | new HashMap<FelixPredicate, HashSet<FelixClause>>(); |
407 | HashMap<FelixPredicate, HashSet<FelixPredicate>> relyOn = |
408 | new HashMap<FelixPredicate, HashSet<FelixPredicate>>(); |
409 | |
410 | for(FelixPredicate fp : fq.getAllOpenPred()){ |
411 | |
412 | testingRules.put(fp, new HashSet<FelixClause>()); |
413 | relyOn.put(fp, new HashSet<FelixPredicate>()); |
414 | |
415 | for(FelixClause fc : fq.getAllClause()){ |
416 | |
417 | if(!fc.getReferencedPredicates().contains(fp)){ |
418 | continue; |
419 | } |
420 | |
421 | if(fc.getLiteralsOfPredicate(fp).size() != 1){ |
422 | continue; |
423 | } |
424 | |
425 | Literal head = fc.getLiteralsOfPredicate(fp).get(0); |
426 | HashSet<Literal> body = new HashSet<Literal>(); |
427 | |
428 | for(Literal l : fc.getRegLiterals()){ |
429 | if(!l.equals(head)){ |
430 | Literal tmpl; |
431 | tmpl = (Literal) l.clone(); |
432 | tmpl.setSense(tmpl.getSense()); |
433 | body.add(tmpl); |
434 | } |
435 | } |
436 | |
437 | boolean isSym = this.isSymmetric(head, body); |
438 | if(isSym == true){ |
439 | System.out.println("\n" + fp.toString() + " is believed to be symmetric by rule " |
440 | + fc.toString()); |
441 | relyOn.put(fp, null); |
442 | }else{ |
443 | body = new HashSet<Literal>(); |
444 | ArrayList<String> open = new ArrayList<String>(); |
445 | HashSet<FelixPredicate> opens = new HashSet<FelixPredicate>(); |
446 | |
447 | for(Literal l : fc.getRegLiterals()){ |
448 | if(l.getPred().isClosedWorld() == true){ |
449 | if(!l.equals(head)){ |
450 | Literal tmpl; |
451 | tmpl = (Literal) l.clone(); |
452 | tmpl.setSense(tmpl.getSense()); |
453 | body.add(tmpl); |
454 | } |
455 | }else{ |
456 | open.add(l.getPred().toString()); |
457 | opens.add((FelixPredicate) l.getPred()); |
458 | } |
459 | } |
460 | |
461 | isSym = this.isSymmetric(head, body); |
462 | |
463 | if(isSym == true){ |
464 | System.out.println("\n" + fp.toString() + " is believed to be symmetric " |
465 | + "conditioned on [" + StringMan.commaList(open) + "]" |
466 | + "by rule " + fc.toString()); |
467 | |
468 | relyOn.put(fp, opens); |
469 | } |
470 | } |
471 | } |
472 | } |
473 | |
474 | System.out.println("Annotation costed " + Timer.elapsedSeconds("pi2p")); |
475 | |
476 | |
477 | } catch (CloneNotSupportedException e) { |
478 | e.printStackTrace(); |
479 | ExceptionMan.die("ERROR - SA-480"); |
480 | } |
481 | |
482 | } |
483 | |
484 | /** |
485 | * Parse predicate which is symmetric. |
486 | */ |
487 | public void parseSymmetricRelation(){ |
488 | |
489 | for(FelixClause fc : fq.getAllClause()){ |
490 | |
491 | if(fc.getRegLiterals().size() != 2 || |
492 | fc.isHardClause() == false){ |
493 | continue; |
494 | } |
495 | |
496 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
497 | |
498 | for(Literal l : fc.getRegLiterals()){ |
499 | |
500 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
501 | |
502 | if(processedPred.contains(p)){ |
503 | continue; |
504 | } |
505 | |
506 | processedPred.add(p); |
507 | |
508 | if(p.isClosedWorld()){ |
509 | continue; |
510 | } |
511 | |
512 | Literal l1 = fc.getRegLiterals().get(0); |
513 | Literal l2 = fc.getRegLiterals().get(1); |
514 | |
515 | if(!l1.getPred().equals(l2.getPred())){ |
516 | continue; |
517 | } |
518 | |
519 | if(p.arity() != 2){ |
520 | continue; |
521 | } |
522 | |
523 | if(l1.getSense() != l2.getSense()){ |
524 | if(l1.getTerms().get(0).toString().equals(l2.getTerms().get(1).toString()) && |
525 | l1.getTerms().get(1).toString().equals(l2.getTerms().get(0).toString()) && |
526 | !l1.getTerms().get(1).toString().equals(l1.getTerms().get(0).toString())){ |
527 | p.registerProperty( |
528 | FPProperty.SYMM, |
529 | fc); |
530 | } |
531 | } |
532 | |
533 | } |
534 | } |
535 | |
536 | } |
537 | |
538 | /** |
539 | * Parse predicate which is reflexive. |
540 | */ |
541 | public void parseReflexiveRelation(){ |
542 | |
543 | for(FelixClause fc : fq.getAllClause()){ |
544 | |
545 | if(fc.getRegLiterals().size() != 1 || |
546 | fc.isHardClause() == false){ |
547 | continue; |
548 | } |
549 | |
550 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
551 | |
552 | for(Literal l : fc.getRegLiterals()){ |
553 | |
554 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
555 | |
556 | if(processedPred.contains(p)){ |
557 | continue; |
558 | } |
559 | |
560 | processedPred.add(p); |
561 | |
562 | if(p.isClosedWorld()){ |
563 | continue; |
564 | } |
565 | |
566 | if(l.getTerms().size() == 2 && |
567 | (l.getSense() == true)){ |
568 | if(l.getTerms().get(0).var() != null && |
569 | l.getTerms().get(0).var().equals(l.getTerms().get(1).var())){ |
570 | p.registerProperty( |
571 | FPProperty.REFLEX, |
572 | fc); |
573 | } |
574 | } |
575 | |
576 | } |
577 | } |
578 | } |
579 | |
580 | /** |
581 | * Parse predicate which is transitive. |
582 | */ |
583 | public void parseTransitiveRelation(){ |
584 | |
585 | for(FelixClause fc : fq.getAllClause()){ |
586 | |
587 | if(fc.getRegLiterals().size() != 3 || |
588 | fc.isHardClause() == false){ |
589 | continue; |
590 | } |
591 | |
592 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
593 | |
594 | for(Literal l : fc.getRegLiterals()){ |
595 | |
596 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
597 | |
598 | if(processedPred.contains(p)){ |
599 | continue; |
600 | } |
601 | |
602 | processedPred.add(p); |
603 | |
604 | if(p.arity() != 2){ |
605 | continue; |
606 | } |
607 | |
608 | if(p.isClosedWorld()){ |
609 | continue; |
610 | } |
611 | |
612 | if(fc.getRegLiterals().size() == 3){ |
613 | |
614 | ArrayList<Literal> ls = new ArrayList<Literal>(); |
615 | ls.add(fc.getRegLiterals().get(0)); |
616 | ls.add(fc.getRegLiterals().get(1)); |
617 | ls.add(fc.getRegLiterals().get(2)); |
618 | |
619 | if(!ls.get(0).getPred().equals(ls.get(1).getPred()) || |
620 | !ls.get(2).getPred().equals(ls.get(1).getPred()) || |
621 | !ls.get(0).getPred().equals(ls.get(2).getPred())){ |
622 | continue; |
623 | } |
624 | |
625 | int head = -1; |
626 | int[] aa = new int[2]; |
627 | int ct = 0; |
628 | for(int i=0;i<3;i++){ |
629 | if(ls.get(i).getSense() == true){ |
630 | if(head != -1){ |
631 | head = -1; |
632 | break; |
633 | } |
634 | head = i; |
635 | }else{ |
636 | if(ct < 2){ |
637 | aa[ct++] = i; |
638 | } |
639 | } |
640 | } |
641 | |
642 | if(head == -1){ |
643 | continue; |
644 | } |
645 | |
646 | Literal l1 = ls.get(aa[0]); |
647 | Literal l2 = ls.get(aa[1]); |
648 | Literal h = ls.get(head); |
649 | |
650 | String common = ""; |
651 | String o1 = ""; |
652 | String o2 = ""; |
653 | for(int i=0;i<2;i++){ |
654 | for(int j=0;j<2;j++){ |
655 | if(l1.getTerms().get(i).toString().equals(l2.getTerms().get(j).toString())){ |
656 | common = l1.getTerms().get(i).toString(); |
657 | o1 = l1.getTerms().get((i+1)%2).toString(); |
658 | o2 = l2.getTerms().get((j+1)%2).toString(); |
659 | break; |
660 | } |
661 | } |
662 | if(common.equals("") == false){ |
663 | break; |
664 | } |
665 | } |
666 | |
667 | if(common.equals("")){ |
668 | continue; |
669 | } |
670 | |
671 | if( h.getTerms().get(0).toString().equals(o1) && h.getTerms().get(1).toString().equals(o2) ){ |
672 | p.registerProperty( |
673 | FPProperty.TRANS, |
674 | fc); |
675 | } |
676 | |
677 | if( h.getTerms().get(1).toString().equals(o1) && h.getTerms().get(0).toString().equals(o2) ){ |
678 | p.registerProperty( |
679 | FPProperty.TRANS, |
680 | fc); |
681 | } |
682 | } |
683 | } |
684 | } |
685 | |
686 | } |
687 | |
688 | /** |
689 | * Parse clause which specifies a CRF chain rule. |
690 | */ |
691 | public void parseChainRecursiveRelation(){ |
692 | |
693 | for(FelixClause fc : fq.getAllClause()){ |
694 | |
695 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
696 | |
697 | for(Literal l : fc.getRegLiterals()){ |
698 | |
699 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
700 | |
701 | if(processedPred.contains(p)){ |
702 | continue; |
703 | } |
704 | |
705 | processedPred.add(p); |
706 | |
707 | if(p.isClosedWorld()){ |
708 | continue; |
709 | } |
710 | |
711 | if(fc.getLiteralsOfPredicate(l.getPred()).size() != 2){ |
712 | continue; |
713 | } |
714 | |
715 | Literal l1 = fc.getLiteralsOfPredicate(l.getPred()).get(0); |
716 | Literal l2 = fc.getLiteralsOfPredicate(l.getPred()).get(1); |
717 | |
718 | boolean isCRFRule = true; |
719 | |
720 | int numberOfDifference = 0; |
721 | for(int i=0;i<l1.getTerms().size();i++){ |
722 | Term t1 = l1.getTerms().get(i); |
723 | Term t2 = l2.getTerms().get(i); |
724 | |
725 | if(t1.toString().equals(t2.toString())){ |
726 | // if these two terms are the same, good! |
727 | continue; |
728 | }else{ |
729 | // if not, we need to see whether in this rule, |
730 | // t1 and t2 is representing a chain. Here we know |
731 | // there can be only one label-field, so, only one |
732 | // such t1-t2 pair can exist. |
733 | |
734 | if(!p.getKeyPositions().contains(i)){ |
735 | continue; |
736 | } |
737 | |
738 | numberOfDifference ++; |
739 | |
740 | boolean isChain = false; |
741 | |
742 | // find in condition [t1 = t2 + 1] |
743 | //TODO: We may want to change it smarter in the future |
744 | for(Expression e : fc.getConstraints()){ |
745 | if(e.toString().equals(t1+" = (" + t2 + " + 1)") || |
746 | e.toString().equals(t2+" = (" + t1 + " + 1)") || |
747 | e.toString().equals("(" + t1 + " + 1) = " + t2) || |
748 | e.toString().equals("(" + t2 + " + 1) = " + t1) || |
749 | e.toString().equals(t1+" = (" + t2 + " - 1)") || |
750 | e.toString().equals(t2+" = (" + t1 + " - 1)") || |
751 | //TODO |
752 | e.toString().equals("(" + t1 + " - 1) = (" + t2 + " + 0)") || |
753 | e.toString().equals("(" + t2 + " - 1) = (" + t1 + " + 0)") || |
754 | e.toString().equals("(" + t1 + " - " + t2 + ") = " + 1) || |
755 | e.toString().equals(1 + " = (" + t1 + " - " + t2 + ")") || |
756 | e.toString().equals("(" + t2 + " - " + t1 + ") = " + 1) || |
757 | e.toString().equals(1 + " = (" + t2 + " - " + t1 + ")")){ |
758 | isChain = true; |
759 | } |
760 | } |
761 | |
762 | if(!isChain){ |
763 | isCRFRule = false; |
764 | } |
765 | |
766 | if(numberOfDifference != 1){ |
767 | isCRFRule = false; |
768 | } |
769 | } |
770 | } |
771 | |
772 | if(isCRFRule == true && numberOfDifference > 0){ |
773 | if(p.getKeyPositions().size() != 0){ |
774 | p.registerProperty( |
775 | FPProperty.CHAIN_RECUR, |
776 | fc); |
777 | } |
778 | } |
779 | |
780 | } |
781 | } |
782 | |
783 | } |
784 | |
785 | // rules other than special rules |
786 | /** |
787 | * Parse clause which does NOT specify 1) NON-RECURSIVE rule and |
788 | * 2) Chain rule. |
789 | * |
790 | */ |
791 | public void parseOtherRecursiveRelation(){ |
792 | for(FelixClause fc : fq.getAllClause()){ |
793 | |
794 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
795 | |
796 | HashSet<FelixPredicate> appeared = new HashSet<FelixPredicate>(); |
797 | |
798 | for(Literal l : fc.getRegLiterals()){ |
799 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
800 | |
801 | if(p.isClosedWorld()){ |
802 | continue; |
803 | } |
804 | |
805 | appeared.add(p); |
806 | } |
807 | |
808 | |
809 | |
810 | |
811 | for(Literal l : fc.getRegLiterals()){ |
812 | |
813 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
814 | |
815 | if(p.isClosedWorld()){ |
816 | continue; |
817 | } |
818 | |
819 | if(processedPred.contains(p)){ |
820 | continue; |
821 | } |
822 | |
823 | processedPred.add(p); |
824 | |
825 | if(appeared.size() == 1){ |
826 | if(fc.getLiteralsOfPredicate(l.getPred()).size() > 1){ |
827 | p.registerProperty( |
828 | FPProperty.OTHER_RECUR, |
829 | fc); |
830 | } |
831 | }else{ |
832 | if(fc.getLiteralsOfPredicate(l.getPred()).size() > 1){ |
833 | p.registerProperty( |
834 | FPProperty.OTHER_RECUR_WITHOTHER_OPENPRED, |
835 | fc); |
836 | } |
837 | } |
838 | |
839 | } |
840 | } |
841 | } |
842 | |
843 | |
844 | /** |
845 | * Parse clause which specifies non-recursive rules. |
846 | */ |
847 | public void parseNonRecursiveRelation(){ |
848 | |
849 | for(FelixClause fc : fq.getAllClause()){ |
850 | |
851 | HashSet<FelixPredicate> processedPred = new HashSet<FelixPredicate>(); |
852 | |
853 | for(Literal l : fc.getRegLiterals()){ |
854 | |
855 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
856 | |
857 | if(p.isClosedWorld()){ |
858 | continue; |
859 | } |
860 | |
861 | if(processedPred.contains(p)){ |
862 | continue; |
863 | } |
864 | |
865 | processedPred.add(p); |
866 | |
867 | if(fc.getLiteralsOfPredicate(l.getPred()).size() == 1){ |
868 | p.registerProperty( |
869 | FPProperty.NON_RECUR, |
870 | fc); |
871 | } |
872 | |
873 | } |
874 | } |
875 | } |
876 | |
877 | /** |
878 | * Parse clause whose weights are specified by embedded weight. |
879 | */ |
880 | public void parseEmbededWeightRule(){ |
881 | |
882 | for(FelixClause fc : fq.getAllClause()){ |
883 | |
884 | for(Literal l : fc.getRegLiterals()){ |
885 | |
886 | FelixPredicate p = fq.getPredByName(l.getPred().getName()); |
887 | |
888 | if(p.isClosedWorld()){ |
889 | continue; |
890 | } |
891 | |
892 | if(fc.hasEmbeddedWeight()){ |
893 | p.registerProperty(FPProperty.EMBED_WEIGHT_RULE, fc); |
894 | } |
895 | |
896 | } |
897 | |
898 | } |
899 | } |
900 | |
901 | } |