[Projects] XRM 82: Fix overlapping detection.

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit &lt;sigoure.benoit(a)lrde.epita.fr&gt; Fix overlapping detection. The code is getting a bit hard to follow [and maintain] probably because it's handling many cases ... but could we make this a lot more generic? :| * src/str/check-meta-vars.str: Consider static const arrays as meta-vars in check-meta-vars (because they are evaluable statically). * src/str/array-decl-desugar.str: Fix the way static arrays are handled. * src/str/collect-static-const-decl.str: Collect only static identifiers, not static array declarations. * src/str/desugar-array-access.str: Ignore duplicate entries. * tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xrm: Fix. * tests/xrm/priorities-exp-array-subscript.xrm: Fix. * tests/xrm/consts.xrm: Fix. * tests/test-xrm-front.sh.in: Change `.xpm' extensions to `.xrm'. * tests/test-parse-xrm.sh.in: Ditto. * tests/test-pp-xrm.sh.in: Ditto. src/str/array-decl-desugar.str | 147 ++++++++++++---- src/str/check-meta-vars.str | 5 src/str/collect-static-const-decl.str | 12 - src/str/desugar-array-access.str | 1 tests/test-parse-xrm.sh.in | 2 tests/test-pp-xrm.sh.in | 4 tests/test-xrm-front.sh.in | 8 tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xrm | 6 tests/xrm/consts.xrm | 2 tests/xrm/priorities-exp-array-subscript.xrm | 2 10 files changed, 141 insertions(+), 48 deletions(-) Index: src/str/check-meta-vars.str --- src/str/check-meta-vars.str (revision 81) +++ src/str/check-meta-vars.str (working copy) @@ -63,6 +63,11 @@ check-all-identifers-are-meta-vars = (?Identifier(_); check-meta-var-declared) + /* it might be a static const array access: */ + <+ (?ArrayAccess(_, _) + ; where(ArrayAccess(id, prism-desugar) + ; ExpandStaticConsts) + ) <+ all(check-all-identifers-are-meta-vars) add-meta-var = Index: src/str/array-decl-desugar.str --- src/str/array-decl-desugar.str (revision 81) +++ src/str/array-decl-desugar.str (working copy) @@ -17,9 +17,12 @@ ** @param build-dec Strategy that will be used to build each declaration. ** The strategy must have the following prototype: ** build-dec(|var-name) + ** @param s Strategy to apply to each of the array accesses. ** @param array-access ArrayAccess at the top of the declaration. + ** @param data When invoking build-dec, set data as current term. */ - array-access-to-dec-list(build-dec: name * c -> r | array-access, data) = + array-access-to-dec-list(build-dec: name * c -> r, s: i * c -> r + | array-access, data) = /* NOTE: This strategy has a weird prototype because build-dec, the strategy * we receive in argument, is a so-called "high order" strategy (eg, not in * the form t -> t). So its "prototype" must be defined here. @@ -27,7 +30,7 @@ * the structure of the type is necessary. The default type of strategy * parameters is a -> b. If a strategy has more formal parameters, then * one need to add "(a -> b)" if this is a strategy, or "a" if it is a - * term parameter.'' -- Martin Bravenboer, iin the stratego mailing list. + * term parameter.'' -- Martin Bravenboer, in the stratego mailing list. * NOTE: This is not documented ATM, hence this comment. Also note that here, * `c' stands for the default argument, eg, the current term. */ @@ -35,7 +38,8 @@ ; <desugar-array-access> array-access => aa-list ; where(check-decl-overlaps-previous-decl(|idf, aa-list) => old-aa-list) ; <conc>(old-aa-list, aa-list) => new-aa-list - ; rules(DeclaredIdentifier: Identifier(idf) -> new-aa-list) + ; rules(DeclaredArrays: Identifier(idf) -> new-aa-list) + ; <s(|idf)> aa-list ; <desugared-array-access-list-to-identifier-list(|idf)> aa-list ; map({var-name: ?var-name @@ -46,7 +50,7 @@ ** Check whether the current array declaration overlaps with a previous ** array declaration. The dimensions declared in the current decl are ** in aa-list. We fetch previously declared dimensions (if any) using the - ** DR DeclaredIdentifier. If one of the dimensions in aa-list is the same + ** DR DeclaredArrays. If one of the dimensions in aa-list is the same ** as one of those previously declared, the current declaration overlaps ** with a previous one (=> error!). ** @@ -54,7 +58,7 @@ ** list otherwise. */ check-decl-overlaps-previous-decl(|idf, aa-list) = - if <DeclaredIdentifier> Identifier(idf) => old-aa-list then + if <DeclaredArrays> Identifier(idf) => old-aa-list then /* Here old-aa-list contains the dimensions already defined for `idf'. */ if !old-aa-list => [_|_] then // if the list is not empty ... /* ... then we already had a definition for that idf, check that @@ -67,7 +71,7 @@ ; map({old-dim: ?old-dim // for each old-dim in old-aa-list... /* ... check whether old-dim is somewhere in aa-list */ - ; <map(try(?old-dim; error-overlapping-dim(|idf, aa-list)))> aa-list + ; <map(try(?old-dim; error-overlapping-dim(|idf, old-aa-list)))> aa-list }) ; !old-aa-list else // return an empty list @@ -77,11 +81,11 @@ ![] end - error-overlapping-dim(|idf, aa-list) = + error-overlapping-dim(|idf, old-aa-list) = err-msg(|["Invalid declaration of array `", idf, "'. This array is ", "declared in multiple parts which overlap."]) ; debug(!"Overlapping dimension: ") - ; <debug(!"Dimensions already declared for that array: ")> aa-list + ; <debug(!"Dimensions already declared for that array: ")> old-aa-list ; <xtc-exit> 5 /** Builders. */ @@ -117,6 +121,22 @@ build-const-bool-no-init(|var-name): [] -> ConstBoolNoInit(Identifier(var-name)) +strategies + + id-proxy(|dummy) = id + + add-dr-for-each-const(|value, idf) = + map({aa: + <repeat(BuildArrayAccess)>(Identifier(idf), <id>) + ; ?aa + ; rules(ExpandStaticConsts: aa -> value) + }) + +rules + + BuildArrayAccess: (a, []) -> a + BuildArrayAccess: (a, [x|xs]) -> (ArrayAccess(a, [Int(x)]), xs) + rules /* @@ -127,31 +147,35 @@ // int without init array-decl-desugar: - IntDecNoInit(aa@ArrayAccess(aa_idf, _), low, up) + IntDecNoInit(aa@ArrayAccess(_, _), low, up) -> dec-list where - array-access-to-dec-list(build-int-dec-no-init | aa, [low, up]) => dec-list + array-access-to-dec-list(build-int-dec-no-init, id-proxy + | aa, [low, up]) => dec-list // int with init array-decl-desugar: - IntDec(aa@ArrayAccess(aa_idf, _), low, up, value) + IntDec(aa@ArrayAccess(_, _), low, up, value) -> dec-list where - array-access-to-dec-list(build-int-dec | aa, [low, up, value]) => dec-list + array-access-to-dec-list(build-int-dec, id-proxy + | aa, [low, up, value]) => dec-list // bool without init array-decl-desugar: - BoolDecNoInit(aa@ArrayAccess(aa_idf, _)) + BoolDecNoInit(aa@ArrayAccess(_, _)) -> dec-list where - array-access-to-dec-list(build-bool-dec-no-init | aa, []) => dec-list + array-access-to-dec-list(build-bool-dec-no-init, id-proxy + | aa, []) => dec-list // bool with init array-decl-desugar: - BoolDec(aa@ArrayAccess(aa_idf, _), value) + BoolDec(aa@ArrayAccess(_, _), value) -> dec-list where - array-access-to-dec-list(build-bool-dec | aa, [value]) => dec-list + array-access-to-dec-list(build-bool-dec, id-proxy + | aa, [value]) => dec-list /* ** ## =================== ## @@ -159,48 +183,105 @@ ** ## =================== ## */ + // const int with init array-decl-desugar: - ConstInt(aa@ArrayAccess(aa_idf, _), value) + ConstInt(aa@ArrayAccess(_, _), value) -> dec-list - where - array-access-to-dec-list(build-const-int | aa, [value]) => dec-list + where <innermost(ExpandStaticConsts + ExpandFormulas)> value => v' + ; !v'{Type("int")} => v + ; let specialized-proxy(|idf) = add-dr-for-each-const(|v, idf) + in array-access-to-dec-list(build-const-int, specialized-proxy + | aa, [v]) => dec-list + end // const int without init array-decl-desugar: - ConstIntNoInit(aa@ArrayAccess(aa_idf, _)) + ConstIntNoInit(aa@ArrayAccess(_, _)) -> dec-list where - array-access-to-dec-list(build-const-int-no-init | aa, []) => dec-list - + array-access-to-dec-list(build-const-int-no-init, id-proxy + | aa, []) => dec-list // const double with init array-decl-desugar: - ConstDouble(aa@ArrayAccess(aa_idf, _), value) + ConstDouble(aa@ArrayAccess(_, _), value) -> dec-list - where - array-access-to-dec-list(build-const-double | aa, [value]) => dec-list + where <innermost(ExpandStaticConsts + ExpandFormulas)> value => v' + ; !v'{Type("double")} => v + ; let specialized-proxy(|idf) = add-dr-for-each-const(|v, idf) + in array-access-to-dec-list(build-const-double, specialized-proxy + | aa, [value]) => dec-list + end // const double without init array-decl-desugar: - ConstDoubleNoInit(aa@ArrayAccess(aa_idf, _)) + ConstDoubleNoInit(aa@ArrayAccess(_, _)) -> dec-list where - array-access-to-dec-list(build-const-double-no-init | aa, []) => dec-list - + array-access-to-dec-list(build-const-double-no-init, id-proxy + | aa, []) => dec-list // const bool with init array-decl-desugar: - ConstBool(aa@ArrayAccess(aa_idf, _), value) + ConstBool(aa@ArrayAccess(_, _), value) -> dec-list - where - array-access-to-dec-list(build-const-bool | aa, [value]) => dec-list + where <innermost(ExpandStaticConsts + ExpandFormulas)> value => v' + ; !v'{Type("bool")} => v + ; let specialized-proxy(|idf) = add-dr-for-each-const(|v, idf) + in array-access-to-dec-list(build-const-bool, specialized-proxy + | aa, [value]) => dec-list + end // const bool without init array-decl-desugar: - ConstBoolNoInit(aa@ArrayAccess(aa_idf, _)) + ConstBoolNoInit(aa@ArrayAccess(_, _)) -> dec-list where - array-access-to-dec-list(build-const-bool-no-init | aa, []) => dec-list + array-access-to-dec-list(build-const-bool-no-init, id-proxy + | aa, []) => dec-list + + +/** +** This section uses array-decl-desugar's traversal to simply collect +** the list of simple variables declared (eg, non array). +** The simple variable declarations are stored in the DR DeclaredIdentifers. +** +** DeclaredIdentifers rewrites an Identifier to a tuple (type, from, to, init) +** where: +** - `type' is either "int" or "bool" +** - `from' and `to' are used to know the range of the variable if it's an +** int. If the variable is a bool, these two fields are unspecified. +** - `init' is the initial value of the variable. If no initial value was +** given when the variable was declared, init = (), the empty tuple, +** which is used a special init value that means no init value. :) +*/ +strategies + +/* +** ## ========== ## +** ## Local vars ## +** ## ========== ## +*/ + + // int without init + array-decl-desugar = + ?IntDecNoInit(idf@Identifier(_), low, up) + ; rules(DeclaredIdentifers: idf -> ("int", low, up, ())) + + // int with init + array-decl-desugar = + ?IntDec(idf@Identifier(_), low, up, value) + ; rules(DeclaredIdentifers: idf -> ("int", low, up, value)) + + // bool without init + array-decl-desugar = + ?BoolDecNoInit(idf@Identifier(_)) + ; rules(DeclaredIdentifers: idf -> ("bool", [], [], ())) + + // bool with init + array-decl-desugar = + ?BoolDec(idf@Identifier(_), value) + ; rules(DeclaredIdentifers: idf -> ("bool", [], [], value)) Index: src/str/collect-static-const-decl.str --- src/str/collect-static-const-decl.str (revision 81) +++ src/str/collect-static-const-decl.str (working copy) @@ -7,25 +7,31 @@ imports signatures inline + array-decl-desugar strategies + // const int collect-static-const-decl = - ?ConstInt(idf, value) + ?ConstInt(idf@Identifier(_), value) ; check-identifier-unicity(|idf) ; where(<innermost(ExpandStaticConsts + ExpandFormulas)> value => v' ; !v'{Type("int")} => v) ; rules(ExpandStaticConsts: idf -> v) + + // const double collect-static-const-decl = - ?ConstDouble(idf, value) + ?ConstDouble(idf@Identifier(_), value) ; check-identifier-unicity(|idf) ; where(<innermost(ExpandStaticConsts + ExpandFormulas)> value => v' ; !v'{Type("double")} => v) ; rules(ExpandStaticConsts: idf -> v) + + // const bool collect-static-const-decl = - ?ConstBool(idf, value) + ?ConstBool(idf@Identifier(_), value) ; check-identifier-unicity(|idf) ; where(<innermost(ExpandStaticConsts + ExpandFormulas)> value => v' ; !v'{Type("bool")} => v) Index: src/str/desugar-array-access.str --- src/str/desugar-array-access.str (revision 81) +++ src/str/desugar-array-access.str (working copy) @@ -85,6 +85,7 @@ * accesses. */ foldr(![], ?(<id>,[]) <+ cartesian-product) end + ; make-set // remove duplicate entries rules Index: tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xrm --- tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xrm (revision 81) +++ tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xrm (working copy) @@ -1,5 +1,5 @@ -for i from 0 to 4 do - for j in 0, 1 do - const int N[i+2+j][0..3] = 0; +for i from 1 to 4 do + for j in 5, 6 do + const int N[i-1][j+1] = 0; end end Index: tests/xrm/priorities-exp-array-subscript.xrm --- tests/xrm/priorities-exp-array-subscript.xrm (revision 81) +++ tests/xrm/priorities-exp-array-subscript.xrm (working copy) @@ -1,7 +1,7 @@ module test x[0..3] : bool init false; y : bool init true; - x[0..4] : [0..42] init 0; + z[0..4] : [0..42] init 0; //[] true -> x[1|1]'=true; [] x[true?2:3]=0 -> true; Index: tests/xrm/consts.xrm --- tests/xrm/consts.xrm (revision 81) +++ tests/xrm/consts.xrm (working copy) @@ -6,5 +6,5 @@ const z[0..5] = 42; const double d[0..3] = 3.14; rate c[0..4] = 42 > 3.14; -probe d[0..4]; +probe e[0..4]; const bool b[0..3] = true; Index: tests/test-xrm-front.sh.in --- tests/test-xrm-front.sh.in (revision 81) +++ tests/test-xrm-front.sh.in (working copy) @@ -22,15 +22,15 @@ outdir="`pwd`" cd .. -for file in `find "$srcdir" -name '*.xpm' | sort`; do +for file in `find "$srcdir" -name '*.xrm' | sort`; do basefile="`basename $file`" - bfile="`echo \"$basefile\" | sed 's/\.x\?pm$//'`" + bfile="`echo \"$basefile\" | sed 's/\.\(xrm\|pm\)$//'`" echo ">>> Starting the test for $basefile" test_cnt=$((test_cnt + 1)) echo @ECHO_N@ " Converting $basefile into standard PRISM AST... " - "@top_builddir@/src/str/xrm-front" -A \ + "@top_builddir@/src/str/xrm-front" -A -po /dev/null \ -i "$file" -o "$outdir/$bfile.pm.aterm" if [ $? -ne 0 ]; then echo 'FAILED, continuing with the next test...' @@ -40,7 +40,7 @@ echo 'OK' echo @ECHO_N@ " Converting $basefile into standard PRISM code ... " - "@top_builddir@/src/str/xrm-front" \ + "@top_builddir@/src/str/xrm-front" -po /dev/null \ -i "$file" -o "$outdir/$bfile.pm" if [ $? -ne 0 ]; then echo 'FAILED, continuing with the next test...' Index: tests/test-parse-xrm.sh.in --- tests/test-parse-xrm.sh.in (revision 81) +++ tests/test-parse-xrm.sh.in (working copy) @@ -14,7 +14,7 @@ srcdir='@srcdir@' rm -f failed_tests.$$ -for file in `find "$srcdir" -name '*.pm' -o -name '*.nm' -o -name '*.sm' -o -name '*.xpm' | sort`; do +for file in `find "$srcdir" -name '*.pm' -o -name '*.nm' -o -name '*.sm' -o -name '*.xrm' | sort`; do echo @ECHO_N@ " Parsing `basename $file` ... " "@top_builddir@/src/tools/parse-xrm" -i "$file" -o /dev/null rv=$? Index: tests/test-pp-xrm.sh.in --- tests/test-pp-xrm.sh.in (revision 81) +++ tests/test-pp-xrm.sh.in (working copy) @@ -22,9 +22,9 @@ outdir="`pwd`" cd .. -for file in `find "$srcdir" -name '*.pm' -o -name '*.nm' -o -name '*.sm' -o -name '*.xpm' | sort`; do +for file in `find "$srcdir" -name '*.pm' -o -name '*.nm' -o -name '*.sm' -o -name '*.xrm' | sort`; do basefile="`basename $file`" - bfile="`echo \"$basefile\" | sed 's/\.x\?pm$//'`" + bfile="`echo \"$basefile\" | sed 's/\.\(xrm\|pm\)$//'`" echo ">>> Starting the test for $basefile" test_cnt=$((test_cnt + 1))