[Axiom-developer] 20070915.02.tpd.patch (bug 100)

[daly]

This code used to cause an infinite loop that eventually killed Axiom.
The bug exists in the intef.spad, in ElementaryIntegration (INTEF),
in the routines lfextendedint and lflimitedint.

The input

  integrate((z^a+1)^b,z)

triggers the bug because of line 2 of each function.
Line 2 of these functions used to read:

      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))


The loop occurs when the call to union causes 

                     a log(z)
                   %e        

to get added to the list every time. This gives the argument to kmax 

                 a log(z)
      arg1= [z,%e        ]

and the result being

        a log(z)
      %e

We keep coming back to process this term, which ends up 
putting the same term back on the list and we loop.
Waldek's solution is to remove the union call. 

If we look at the original problem we see:
integrate((z^a+1)^b,z)

           z
         ++     a     b
   (1)   |   (%I  + 1) d%I
        ++
                                          Type: Union(Expression Integer,...)

and if we replace %I by z we get the original expression

           z
         ++    a     b
         |   (z  + 1) dz
        ++


=========================================================================
diff --git a/changelog b/changelog
index d6c0bdd..9baab4b 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,7 @@
+20070915 tpd merge bug100 branch
+20070915 tpd src/input/Makefile add bug100.input regression test
+20070915 tpd src/input/bug100.input test integrate((z^a+1)^b,z) infinite loop
+20070915 wxh src/algebra/intef.spad fix integrate((z^a+1)^b,z) infinite loop
 20070915 tpd src/algebra/carten minor edit for regression cleanup
 20070914 wxh src/hyper/hyper fix bad bracing of )hd change
 20070914 tpd src/algebra/fraction.spad remove double )spool command
diff --git a/src/algebra/intef.spad.pamphlet b/src/algebra/intef.spad.pamphlet
index 4dbbc26..955d284 100644
--- a/src/algebra/intef.spad.pamphlet
+++ b/src/algebra/intef.spad.pamphlet
@@ -227,9 +227,41 @@ ElementaryIntegration(R, F): Exports == Implementation 
where
         algint(f, t, y, differentiate(#1, differentiate(#1, x),
                                             differentiate(t::F, x)::UP))
 
+@
+Bug \#100 is an infinite loop that eventually kills Axiom 
+from the input
+\begin{verbatim}
+  integrate((z^a+1)^b,z)
+\end{verbatim}
+
+Line 2 of this function used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes 
+\begin{verbatim}
+                     a log(z)
+                   %e        
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax 
+\begin{verbatim}
+                 a log(z)
+      arg1= [z,%e        ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+        a log(z)
+      %e
+\end{verbatim}
+We keep coming back to process this term, which ends up 
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call. 
+
+<<package INTEF ElementaryIntegration>>=
     lfextendedint(f, x, g) ==
       empty?(l := varselect(kernels f, x)) => [x::F * f, 0]
-      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+      symbolIfCan(k := kmax(l))
         case SE =>
           map(multivariate(#1, k), extendedint(univariate(f, k),
                                                univariate(g, k)))
@@ -238,9 +270,16 @@ ElementaryIntegration(R, F): Exports == Implementation 
where
       has?(operator k, ALGOP) => alglfextint(f, k, l, x, g)
       unkextint(f, x, g)
 
+@
+This is part of the fix for bug 100. Line 2 of this function used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+\end{verbatim}
+See the above discussion for why this causes an infinite loop.
+<<package INTEF ElementaryIntegration>>=
     lflimitedint(f, x, lu) ==
       empty?(l := varselect(kernels f, x)) => [x::F * f, empty()]
-      symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+      symbolIfCan(k := kmax(l)) case SE =>
        map(multivariate(#1, k), limitedint(univariate(f, k),
                                         [univariate(u, k) for u in lu]))
       is?(k, "exp"::SE) => explimint(f, x, k, lu)
diff --git a/src/input/Makefile.pamphlet b/src/input/Makefile.pamphlet
index 16a3b98..92c1dc5 100644
--- a/src/input/Makefile.pamphlet
+++ b/src/input/Makefile.pamphlet
@@ -287,7 +287,7 @@ REGRES= algaggr.regress algbrbf.regress  algfacob.regress 
alist.regress  \
     arrows.regress    assign.regress   atansqrt.regress \
     asec.regress      bags.regress      bbtree.regress \
     binary.regress    bop.regress      bstree.regress   bouquet.regress \
-    bug10069.regress \
+    bug100.regress    bug10069.regress \
     bugs.regress      bug10312.regress bug6357.regress  bug9057.regress \
     calcprob.regress  \
     calculus2.regress calculus.regress cardinal.regress card.regress \
@@ -502,7 +502,8 @@ FILES= ${OUT}/algaggr.input  ${OUT}/algbrbf.input    
${OUT}/algfacob.input \
        ${OUT}/bags.input     ${OUT}/bbtree.input     ${OUT}/bern.input \
        ${OUT}/bernpoly.input ${OUT}/binary.input     ${OUT}/bop.input \
        ${OUT}/bouquet.input  ${OUT}/bstree.input     ${OUT}/bug6357.input \
-       ${OUT}/bug9057.input  ${OUT}/bug10069.input   ${OUT}/bug10312.input \
+       ${OUT}/bug9057.input  ${OUT}/bug100.input \
+       ${OUT}/bug10069.input ${OUT}/bug10312.input \
        ${OUT}/calcprob.input ${OUT}/calculus.input \
        ${OUT}/cardinal.input ${OUT}/card.input       ${OUT}/carten.input \
        ${OUT}/cclass.input   ${OUT}/cdraw.input      ${OUT}/char.input \
@@ -677,6 +678,7 @@ DOCFILES= \
   ${DOC}/bernpoly.input.dvi    ${DOC}/binary.input.dvi     \
   ${DOC}/bop.input.dvi         ${DOC}/bouquet.input.dvi    \
   ${DOC}/bstree.input.dvi      ${DOC}/bug10069.input.dvi   \
+  ${DOC}/bug100.input.dvi \
   ${DOC}/bug10312.input.dvi    ${DOC}/bug6357.input.dvi    \
   ${DOC}/bug9057.input.dvi     ${DOC}/bugs.input.dvi       \
   ${DOC}/c02aff.input.dvi      ${DOC}/c02agf.input.dvi     \
diff --git a/src/input/bug100.input.pamphlet b/src/input/bug100.input.pamphlet
new file mode 100644
index 0000000..799d339
--- /dev/null
+++ b/src/input/bug100.input.pamphlet
@@ -0,0 +1,80 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/input bug100.input}
+\author{Timothy Daly}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+@
+This code used to cause an infinite loop that eventually killed Axiom.
+The bug exists in the {\tt intef.spad}, in ElementaryIntegration (INTEF),
+in the routines {\tt lfextendedint} and {\tt lflimitedint}.
+
+The input
+\begin{verbatim}
+  integrate((z^a+1)^b,z)
+\end{verbatim}
+triggers the bug because of line 2 of each function.
+Line 2 of these functions used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes 
+\begin{verbatim}
+                     a log(z)
+                   %e        
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax 
+\begin{verbatim}
+                 a log(z)
+      arg1= [z,%e        ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+        a log(z)
+      %e
+\end{verbatim}
+We keep coming back to process this term, which ends up 
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call. 
+
+<<*>>=
+)spool bug100.output
+)set message test on
+)set message auto off
+)clear all
+ 
+--S 1 of 1
+integrate((z^a+1)^b,z)
+--R
+--R           z
+--R         ++     a     b
+--R   (1)   |   (%I  + 1) d%I
+--R        ++
+--R                                          Type: Union(Expression 
Integer,...)
+--E 1
+@
+If we substitute z for %I we get:
+\begin{verbatim}
+           z
+         ++    a     b
+         |   (z  + 1) dz
+        ++
+
+\end{verbatim}
+which is the original input integral.
+<<*>>=
+)spool 
+)lisp (bye)
+ 
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}