Merge lp:~zorba-coders/zorba/caching into lp:zorba

[Matthias Brantner]

- automatic caching of recursive, non-sequential, and deterministic functions with atomic parameter and return types
- %ann:cache and %ann:no-cache for controlling function result caching

- automatic caching of recursive, non-sequential, and deterministic functions with atomic parameter and return types
- %ann:cache and %ann:no-cache for controlling function result caching

[Zorba Build Bot (zorba-buildbot)]

Validation queue starting for merge proposal.
Log at: http://zorbatest.lambda.nu:8080/remotequeue/caching-2011-11-04T17-29-08.827Z/log.html

[Zorba Build Bot (zorba-buildbot)]

The attempt to merge lp:~matthias-brantner/zorba/caching into lp:zorba failed. Below is the output from the failed tests.

CMake Error at /home/ceej/zo/testing/zorbatest/tester/TarmacLander.cmake:272 (message):
  Validation queue job caching-2011-11-04T17-29-08.827Z is finished. The
  final status was:

  31 tests did not succeed - changes not commited.

Error in read script: /home/ceej/zo/testing/zorbatest/tester/TarmacLander.cmake

[Markos Zaharioudakis (markos-za)]

Here are a few problems I can see so far:

1. I don't think we can do function caching for variadic functions. The current implementation of user_function::computeResultCaching certainly does not support variadic functions, but more importantly, we need a fixed number of params to form the index key (unless we start thinking towards having more than one cache for variadic functions).

2. The user_function::computeResultCaching does the full computation every time it is invoked (and it may be invoked multiple times from the codegen). It should cache the result of the 1st computation and simply return it afterwards.

3. In UDFunctionCallIterator::createCache, the line:
   lSpec.theKeyTypes[i] = sig[i]->get_qname().getp();
is not correct if the type of the param is a user-defined type (because the store will not understand its name). You must call getBaseBuiltinType() of the param type first (like the translator does in line 4401).

4. It's probably worthwhile to do something so that we don't have to recompute the args in case of a cache miss. What we have to do is create a temp sequence for each arg, and fill it with the corresponding arg value; then bind the arg reference to that temp seq, instead the arg wrapper.

5. It's probably worthwhile to allow subtypes of xs:anyAtomicType? as param types. Index creation already supports "null" keys, but we will need a new probe function. This we should probably do as a phase-2 task.

[Matthias Brantner (matthias-brantner)]

Adressed comments 1-4.

[Matthias Brantner (matthias-brantner)]

review: Approve

[Zorba Build Bot (zorba-buildbot)]

There are additional revisions which have not been approved in review. Please seek review and approval of these new revisions.

[Zorba Build Bot (zorba-buildbot)]

Validation queue starting for merge proposal.
Log at: http://zorbatest.lambda.nu:8080/remotequeue/caching-2011-11-21T22-11-29.225Z/log.html

[Zorba Build Bot (zorba-buildbot)]

The attempt to merge lp:~matthias-brantner/zorba/caching into lp:zorba failed. Below is the output from the failed tests.

CMake Error at /home/ceej/zo/testing/zorbatest/tester/TarmacLander.cmake:272 (message):
  Validation queue job caching-2011-11-21T22-11-29.225Z is finished. The
  final status was:

  3 tests did not succeed - changes not commited.

Error in read script: /home/ceej/zo/testing/zorbatest/tester/TarmacLander.cmake

[Markos Zaharioudakis (markos-za)]

Matthias, can you change the ownership to zorba-coders so that I can do some small changes (documentation and style)?

[Markos Zaharioudakis (markos-za)]

I think there is a bug in user_function::computeResultCaching, starting at line 542. The condition: if (lExplicitCacheRequest) appears twice and theCacheResults will actually be set to true if the udf is sequential or non-deterministic.

[Matthias Brantner (matthias-brantner)]

review: Approve

[Zorba Build Bot (zorba-buildbot)]

Attempt to merge into lp:zorba failed due to conflicts:

text conflict in ChangeLog
text conflict in src/context/static_context_consts.h

[lp:~zorba-coders/zorba/caching]

10540. By Matthias Brantner on 2011-12-09

merge with trunk

10541. By Matthias Brantner on 2011-12-12

merge with trunk

10542. By Matthias Brantner on 2011-12-13

merge

Unmerged revisions

=== modified file 'ChangeLog'
--- ChangeLog	2011-11-16 04:00:29 +0000
+++ ChangeLog	2011-11-19 17:32:30 +0000
@@ -54,6 +54,8 @@
     xs:anyAtomicType or xs:untypedAtomic.
   * Added undo for node revalidation
   * Optimization for count(collection()) expressions
+  * Caching of results for recursive functions with atomic parameter and return types.
+  * Added %ann:cache and %ann:no-cache to enable or disable caching of results of functions with atomic parameter and return types.
   * Fixed bug #867133 (SWIG PHP build failure on Mac OSX)
   * Fixed bug #872796  (validate-in-place can interfere with other update primitives)
   * Fixed bug #872799 (validate-in-place can set incorrect types)

=== modified file 'doc/zorba/options.dox'
--- doc/zorba/options.dox	2011-09-14 06:15:19 +0000
+++ doc/zorba/options.dox	2011-11-19 17:32:30 +0000
@@ -278,6 +278,27 @@
 In order to be able to use the value twice, the <tt>string:materialize</tt> function must be used to materialize the entire contents of the file <tt>myfile.txt</tt> in memory.
 Otherwise, the error zerr:ZSTR0055 is raised.
 
+\paragraph caching_annotation Caching Results of Functions
+Caching of function results might improve the performance if computational expensive functions are invoked multiple times with the same arguments.
+
+Zorba automatically caches results of recursive, deterministic, and non-sequential functions whose parameter and return types are subtypes of xs:anyAtomicType if at least optimization level O1 is used.
+Specifically, if such a function is called twice with the same arguments, the result of the second call will return the same value without re-evaluating the function.
+
+For example, in the following recursive function computing a fibonacci number, each result is automatically cached and, hence, dramatically improves the performance.
+
+\include zorba/udf/udf-fib-rec.xq
+
+Specifically, this optimization reduces the complexity of the function from O(1.6^n) to O(n).
+
+In order to explicitly disable function caching, the user can specify the <tt>%ann:no-cache</tt> annotation.
+
+In addition, the user can use the <tt>%ann:cache</tt> annotation to cache the results of functions other than the ones that are automatically cached.
+However, this will only work if the function is not updating and its parameter and return types are subtypes of xs:anyAtomicType.
+Zorba will raise a warning if caching is explicitly enabled but the function does not meet this criteria (zwarn:ZWST0005).
+
+Please note, that explicitly enforcing caching for sequential or nondeterministic functions might not give the intended result.
+In such cases, Zorba will raise a warning (zwarn:ZWST0006).
+
 \paragraph collection_index_annotations Annotations on Collections and Indexes
 
 The \ref xqddf uses annotations to assign properties to collections and indexes.

=== modified file 'include/zorba/pregenerated/diagnostic_list.h'
--- include/zorba/pregenerated/diagnostic_list.h	2011-11-15 08:23:20 +0000
+++ include/zorba/pregenerated/diagnostic_list.h	2011-11-19 17:32:30 +0000
@@ -600,6 +600,8 @@
 
 extern ZORBA_DLL_PUBLIC ZorbaErrorCode ZDDY0034_INDEX_RANGE_VALUE_PROBE_BAD_KEY_TYPES;
 
+extern ZORBA_DLL_PUBLIC ZorbaErrorCode ZDDY0035_INDEX_GENERAL_INSERT;
+
 extern ZORBA_DLL_PUBLIC ZorbaErrorCode ZDDY0031_IC_NOT_DECLARED;
 
 extern ZORBA_DLL_PUBLIC ZorbaErrorCode ZDDY0032_IC_NOT_ACTIVATED;
@@ -752,6 +754,10 @@
 
 extern ZORBA_DLL_PUBLIC ZorbaWarningCode ZWST0004_AMBIGUOUS_SEQUENTIAL_FLWOR;
 
+extern ZORBA_DLL_PUBLIC ZorbaWarningCode ZWST0005_CACHING_NOT_POSSIBLE;
+
+extern ZORBA_DLL_PUBLIC ZorbaWarningCode ZWST0006_CACHING_MIGHT_NOT_BE_INTENDED;
+
 } // namespace zwarn
 } // namespace zorba
 #endif /* ZORBA_DIAGNOSTIC_LIST_API_H */

=== modified file 'modules/com/zorba-xquery/www/modules/pregenerated/errors.xq'
--- modules/com/zorba-xquery/www/modules/pregenerated/errors.xq	2011-11-15 08:23:20 +0000
+++ modules/com/zorba-xquery/www/modules/pregenerated/errors.xq	2011-11-19 17:32:30 +0000
@@ -501,6 +501,10 @@
 
 (:~
 :)
+declare variable $zerr:ZDDY0035 as xs:QName := fn:QName($zerr:NS, "zerr:ZDDY0035");
+
+(:~
+:)
 declare variable $zerr:ZDDY0031 as xs:QName := fn:QName($zerr:NS, "zerr:ZDDY0031");
 
 (:~

=== modified file 'modules/com/zorba-xquery/www/modules/pregenerated/warnings.xq'
--- modules/com/zorba-xquery/www/modules/pregenerated/warnings.xq	2011-11-15 08:10:49 +0000
+++ modules/com/zorba-xquery/www/modules/pregenerated/warnings.xq	2011-11-19 17:32:30 +0000
@@ -53,4 +53,23 @@
 
 (:~
 :)
-declare variable $zwarn:ZWST0004 as xs:QName := fn:QName($zwarn:NS, "zwarn:ZWST0004");
\ No newline at end of file
+declare variable $zwarn:ZWST0004 as xs:QName := fn:QName($zwarn:NS, "zwarn:ZWST0004");
+
+(:~
+ :
+ : This warning is raised if the user explicitly enables caching
+ : of function results (using the %ann:cache annotation) but the function
+ : is updating or its parameter and return types are not subtypes of
+ : xs:anyAtomicType.
+ : 
+:)
+declare variable $zwarn:ZWST0005 as xs:QName := fn:QName($zwarn:NS, "zwarn:ZWST0005");
+
+(:~
+ :
+ : This warning is raised if the user explicitly enables caching
+ : of function results (using the %ann:cache annotation) and the function
+ : is annotated as sequential or nondeterministic.
+ : 
+:)
+declare variable $zwarn:ZWST0006 as xs:QName := fn:QName($zwarn:NS, "zwarn:ZWST0006");
\ No newline at end of file

=== modified file 'src/annotations/annotations.cpp'
--- src/annotations/annotations.cpp	2011-11-07 06:32:00 +0000
+++ src/annotations/annotations.cpp	2011-11-19 17:32:30 +0000
@@ -100,6 +100,9 @@
 
   ZANN(streamable, streamable);
 
+  ZANN(cache, cache);
+  ZANN(no-cache, nocache);
+
   //
   // Zorba annotations - xqddf
   //
@@ -168,6 +171,10 @@
       ZANN(zann_nonsequential));
 
   theRuleSet.push_back(
+      ZANN(zann_cache) |
+      ZANN(zann_nocache));
+
+  theRuleSet.push_back(
       ZANN(fn_private) |
       ZANN(fn_public));
 
@@ -433,6 +440,5 @@
 }
 
 
-
 } /* namespace zorba */
 /* vim:set et sw=2 ts=2: */

=== modified file 'src/annotations/annotations.h'
--- src/annotations/annotations.h	2011-11-01 13:47:10 +0000
+++ src/annotations/annotations.h	2011-11-19 17:32:30 +0000
@@ -55,6 +55,8 @@
     zann_nonassignable,
     zann_sequential,
     zann_nonsequential,
+    zann_cache,
+    zann_nocache,
     zann_variadic,
     zann_streamable,
     zann_unique,

=== modified file 'src/compiler/codegen/plan_visitor.cpp'
--- src/compiler/codegen/plan_visitor.cpp	2011-10-24 02:42:07 +0000
+++ src/compiler/codegen/plan_visitor.cpp	2011-11-19 17:32:30 +0000
@@ -98,6 +98,7 @@
 #endif
 
 #include "functions/function.h"
+#include "functions/udf.h"
 #include "functions/library.h"
 
 #include "types/typeops.h"
@@ -2283,11 +2284,14 @@
           dynamic_cast<EnclosedIterator*>(iter.getp())->setInUpdateExpr();
       }
     }
-#if 0
     else if (func->isUdf())
     {
+      // need to computeResultCaching here for iterprint to work
       const user_function* udf = static_cast<const user_function*>(func);
+      udf->computeResultCaching(theCCB->theXQueryDiagnostics);
+    }
 
+#if 0
       if (udf->isExiting())
       {
         TypeManager* tm = v.get_type_manager();

=== modified file 'src/context/static_context_consts.h'
--- src/context/static_context_consts.h	2011-07-21 23:02:27 +0000
+++ src/context/static_context_consts.h	2011-11-19 17:32:30 +0000
@@ -132,6 +132,8 @@
     zann_nonsequential,
     zann_variadic,
     zann_streamable,
+    zann_cache,
+    zann_no_cache,
     zann_unique,
     zann_nonunique,
     zann_value_equality,

=== modified file 'src/diagnostics/diagnostic_en.xml'
--- src/diagnostics/diagnostic_en.xml	2011-11-15 08:23:20 +0000
+++ src/diagnostics/diagnostic_en.xml	2011-11-19 17:32:30 +0000
@@ -1997,6 +1997,10 @@
       <value>"$1": index range-value probe has search keys with incompatible types</value>
     </diagnostic>
 
+    <diagnostic code="ZDDY0035" name="INDEX_GENERAL_INSERT">
+      <value>"$1": index inserting more than one key not allowed for general index</value>
+    </diagnostic>
+
     <diagnostic code="ZDDY0031" name="IC_NOT_DECLARED">
       <value>"$1": integrity constraint is not declared</value>
     </diagnostic>
@@ -2307,6 +2311,37 @@
       <value>Sequential FLWOR expr may not have the semantics you expect</value>
     </diagnostic>
 
+    <diagnostic code="ZWST0005" name="CACHING_NOT_POSSIBLE">
+      <comment>
+        This warning is raised if the user explicitly enables caching
+        of function results (using the %ann:cache annotation) but the function
+        is updating or its parameter and return types are not subtypes of
+        xs:anyAtomicType.
+      </comment>
+      <value>"$1": function caching not possible; $2</value>
+      <entry key="RETURN_TYPE">
+        <value>return type ($3) is not subtype of xs:anyAtomicType</value>
+      </entry>
+      <entry key="PARAM_TYPE">
+        <value>type of parameter $3 is $4 which is not a subtype of xs:anyAtomicType</value>
+      </entry>
+      <entry key="UPDATING">
+        <value>function is updating</value>
+      </entry>
+      <entry key="VARIADIC">
+        <value>function is variadic</value>
+      </entry>
+    </diagnostic>
+
+    <diagnostic code="ZWST0006" name="CACHING_MIGHT_NOT_BE_INTENDED">
+      <comment>
+        This warning is raised if the user explicitly enables caching
+        of function results (using the %ann:cache annotation) and the function
+        is annotated as sequential or nondeterministic.
+      </comment>
+      <value>"$1": function caching might not give the intended result because the function is declared as $2</value>
+    </diagnostic>
+
   </namespace>
 
   <!--////////// Subvalues /////////////////////////////////////////////////-->

=== modified file 'src/diagnostics/pregenerated/diagnostic_list.cpp'
--- src/diagnostics/pregenerated/diagnostic_list.cpp	2011-11-15 08:23:20 +0000
+++ src/diagnostics/pregenerated/diagnostic_list.cpp	2011-11-19 17:32:30 +0000
@@ -879,6 +879,9 @@
 ZorbaErrorCode ZDDY0034_INDEX_RANGE_VALUE_PROBE_BAD_KEY_TYPES( "ZDDY0034" );
 
 
+ZorbaErrorCode ZDDY0035_INDEX_GENERAL_INSERT( "ZDDY0035" );
+
+
 ZorbaErrorCode ZDDY0031_IC_NOT_DECLARED( "ZDDY0031" );
 
 
@@ -1104,6 +1107,12 @@
 ZorbaWarningCode ZWST0004_AMBIGUOUS_SEQUENTIAL_FLWOR( "ZWST0004" );
 
 
+ZorbaWarningCode ZWST0005_CACHING_NOT_POSSIBLE( "ZWST0005" );
+
+
+ZorbaWarningCode ZWST0006_CACHING_MIGHT_NOT_BE_INTENDED( "ZWST0006" );
+
+
 } // namespace zwarn
 
 } // namespace zorba

=== modified file 'src/diagnostics/pregenerated/dict_en.cpp'
--- src/diagnostics/pregenerated/dict_en.cpp	2011-11-15 08:23:20 +0000
+++ src/diagnostics/pregenerated/dict_en.cpp	2011-11-19 17:32:30 +0000
@@ -297,6 +297,7 @@
   { "ZDDY0032", "\"$1\": integrity constraint is not activated" },
   { "ZDDY0033", "\"$1\": integrity constraint not met for collection \"$2\"" },
   { "ZDDY0034", "\"$1\": index range-value probe has search keys with incompatible types" },
+  { "ZDDY0035", "\"$1\": index inserting more than one key not allowed for general index" },
   { "ZDST0001", "\"$1\": collection already declared" },
   { "ZDST0002", "\"$1\": collection already imported into module \"$2\"" },
   { "ZDST0003", "\"$1\": collection declaration not allowed in main module" },
@@ -359,6 +360,8 @@
   { "ZWST0002", "\"$1\": unknown or unsupported annotation" },
   { "ZWST0003", "\"$1\": function declared sequential, but has non-sequential body" },
   { "ZWST0004", "Sequential FLWOR expr may not have the semantics you expect" },
+  { "ZWST0005", "\"$1\": function caching not possible; $2" },
+  { "ZWST0006", "\"$1\": function caching might not give the intended result because the function is declared as $2" },
   { "ZXQD0001", "\"$1\": prefix not declared when calling function \"$2\" from $3" },
   { "ZXQD0002", "\"$1\": $2" },
   { "ZXQD0003", "inconsistent options to the parse-xml-fragment() function: $1" },
@@ -663,6 +666,10 @@
   { "~XUST0002_UDF_2", "\"$2\": function declared updating but body is not updating or vacuous" },
   { "~ZDST0060_unknown_localname", "unknown localname ($3)" },
   { "~ZDST0060_unknown_namespace", "unknown namespace ($3)" },
+  { "~ZWST0005_PARAM_TYPE", "type of parameter $3 is $4 which is not a subtype of xs:anyAtomicType" },
+  { "~ZWST0005_RETURN_TYPE", "return type ($3) is not subtype of xs:anyAtomicType" },
+  { "~ZWST0005_UPDATING", "function is updating" },
+  { "~ZWST0005_VARIADIC", "function is variadic" },
   { "~ZXQD0004_NON_NEGATIVE", "given value must be non-negative ($2)" },
   { "~ZXQD0004_NOT_WITHIN_RANGE", "not within allowed range ($2)" },
   { "~ZXQP0004_TypeOps_is_in_scope_ForFunctionItemTypes", "TypeOps::is_in_scope() for function-item types" },

=== modified file 'src/functions/udf.cpp'
--- src/functions/udf.cpp	2011-10-18 17:37:41 +0000
+++ src/functions/udf.cpp	2011-11-19 17:32:30 +0000
@@ -26,10 +26,15 @@
 #include "compiler/rewriter/framework/rewriter.h"
 
 #include "functions/udf.h"
+#include "annotations/annotations.h"
 #include "functions/function_impl.h"
 
+#include "diagnostics/xquery_warning.h"
+
 #include "types/typeops.h"
 
+#include "store/api/index.h" // needed for destruction of the cache
+
 
 namespace zorba
 {
@@ -54,7 +59,10 @@
   theIsExiting(false),
   theIsLeaf(true),
   theIsOptimized(false),
-  thePlanStateSize(0)
+  thePlanStateSize(0),
+  theCache(0),
+  theCacheResults(false),
+  theCacheComputed(false)
 {
   setFlag(FunctionConsts::isUDF);
   resetFlag(FunctionConsts::isBuiltin);
@@ -318,7 +326,7 @@
 /*******************************************************************************
 
 ********************************************************************************/
-  PlanIter_t user_function::getPlan(CompilerCB* ccb, uint32_t& planStateSize)
+PlanIter_t user_function::getPlan(CompilerCB* ccb, uint32_t& planStateSize)
 {
   if (thePlan == NULL)
   {
@@ -372,9 +380,207 @@
 /*******************************************************************************
 
 ********************************************************************************/
-CODEGEN_DEF(user_function)
-{
-  return new UDFunctionCallIterator(aSctx, aLoc, aArgs, this);
+store::Index* user_function::getCache() const
+{
+  return theCache;
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
+void user_function::setCache(store::Index* aCache)
+{
+  theCache = aCache;
+}
+
+
+/*******************************************************************************
+********************************************************************************/
+bool user_function::cacheResults() const
+{
+  return theCacheResults;
+}
+
+
+/*******************************************************************************
+ only cache recursive (non-sequential, non-updating, deterministic)
+ functions with singleton atomic input and output
+********************************************************************************/
+void user_function::computeResultCaching(XQueryDiagnostics* diag) const
+{
+  if (theCacheComputed)
+  {
+    return; 
+  }
+
+  struct OnExit {
+  private:
+    bool& theResult;
+    bool& theCacheComputed;
+
+  public:
+    OnExit(bool& aResult, bool& aCacheComputed)
+      : theResult(aResult),
+        theCacheComputed(aCacheComputed) {}
+
+    void cache() { theResult = true; }
+
+    ~OnExit()
+    {
+      theCacheComputed = true;
+    }
+  };
+
+  // will be destroyed when the function is exited
+  // set caching to true if cache() is called
+  OnExit lExit(theCacheResults, theCacheComputed);
+
+  // check necessary conditions
+  // %ann:cache or not %ann:no-cache
+  if (theAnnotationList && theAnnotationList->contains(AnnotationInternal::zann_nocache))
+  {
+    return;
+  }
+
+  // was the %ann:cache annotation given explicitly by the user
+  bool lExplicitCacheRequest = theAnnotationList
+    ?theAnnotationList->contains(AnnotationInternal::zann_cache)
+    :false;
+
+  if (isVariadic())
+  {
+    if (lExplicitCacheRequest)
+    {
+      diag->add_warning(
+        NEW_XQUERY_WARNING(
+          zwarn::ZWST0005_CACHING_NOT_POSSIBLE,
+          WARN_PARAMS(
+            getName()->getStringValue(),
+            ZED( ZWST0005_VARIADIC )
+          ),
+          WARN_LOC(theLoc)
+        )
+      );
+    }
+    return;
+  }
+
+  // parameter and return types are subtype of xs:anyAtomicType?
+  const xqtref_t& lRes = theSignature.returnType();
+  TypeManager* tm = lRes->get_manager();
+
+  if (!TypeOps::is_subtype(tm,
+                           *lRes,
+                           *GENV_TYPESYSTEM.ANY_ATOMIC_TYPE_ONE,
+                           theLoc))
+  {
+    if (lExplicitCacheRequest)
+    {
+      diag->add_warning(
+        NEW_XQUERY_WARNING(
+          zwarn::ZWST0005_CACHING_NOT_POSSIBLE,
+          WARN_PARAMS(
+            getName()->getStringValue(),
+            ZED( ZWST0005_RETURN_TYPE ),
+            lRes->toString()
+          ),
+          WARN_LOC(theLoc)
+        )
+      );
+    }
+    return;
+  }
+
+  size_t lArity = theSignature.paramCount();
+  for (size_t i = 0; i < lArity; ++i)
+  {
+    const xqtref_t& lArg = theSignature[i];
+    if (!TypeOps::is_subtype(tm,
+                             *lArg,
+                             *GENV_TYPESYSTEM.ANY_ATOMIC_TYPE_ONE,
+                             theLoc))
+    {
+      if (lExplicitCacheRequest)
+      {
+        diag->add_warning(
+          NEW_XQUERY_WARNING(
+            zwarn::ZWST0005_CACHING_NOT_POSSIBLE,
+            WARN_PARAMS(
+              getName()->getStringValue(),
+              ZED( ZWST0005_PARAM_TYPE ),
+              i+1,
+              lArg->toString()
+            ),
+            WARN_LOC(theLoc)
+          )
+        );
+      }
+      return;
+    }
+  }
+
+  // function updating?
+  if (isUpdating())
+  {
+    if (lExplicitCacheRequest)
+    {
+      diag->add_warning(
+        NEW_XQUERY_WARNING(
+          zwarn::ZWST0005_CACHING_NOT_POSSIBLE,
+          WARN_PARAMS(
+            getName()->getStringValue(),
+            ZED( ZWST0005_UPDATING )
+          ),
+          WARN_LOC(theLoc)
+        )
+      );
+    }
+    return;
+  }
+
+  if (lExplicitCacheRequest)
+  {
+    if (isSequential() || !isDeterministic())
+    {
+      if (lExplicitCacheRequest)
+      {
+        diag->add_warning(
+          NEW_XQUERY_WARNING(
+            zwarn::ZWST0006_CACHING_MIGHT_NOT_BE_INTENDED,
+            WARN_PARAMS(
+              getName()->getStringValue(),
+              (isSequential()?"sequential":"non-deterministic")
+            ),
+            WARN_LOC(theLoc)
+          )
+        );
+      }
+    }
+    lExit.cache();
+    return;
+  }
+
+  // optimization is prerequisite before invoking isRecursive
+  if (!lExplicitCacheRequest && isOptimized() && !isRecursive())
+  {
+    return;
+  }
+
+  lExit.cache();
+}
+
+/*******************************************************************************
+
+********************************************************************************/
+PlanIter_t user_function::codegen(
+      CompilerCB* cb,
+      static_context* sctx,
+      const QueryLoc& loc,
+      std::vector<PlanIter_t>& argv,
+      AnnotationHolder& ann) const
+{
+  return new UDFunctionCallIterator(sctx, loc, argv, this);
 }
 
 

=== modified file 'src/functions/udf.h'
--- src/functions/udf.h	2011-10-18 17:37:41 +0000
+++ src/functions/udf.h	2011-11-19 17:32:30 +0000
@@ -25,6 +25,12 @@
 namespace zorba 
 {
 
+  namespace store
+  {
+    class Index;
+    typedef rchandle<Index> Index_t;
+  }
+
 
 /*******************************************************************************
   A udf with params $x1, $x2, ..., $xn and a body_expr is translated into a
@@ -102,6 +108,10 @@
   uint32_t                    thePlanStateSize;
   std::vector<ArgVarRefs>     theArgVarsRefs;
 
+  mutable store::Index_t      theCache;
+  mutable bool                theCacheResults;
+  mutable bool                theCacheComputed;
+
 public:
   SERIALIZABLE_CLASS(user_function)
   user_function(::zorba::serialization::Archiver& ar);
@@ -160,12 +170,21 @@
 
   const std::vector<ArgVarRefs>& getArgVarsRefs() const;
 
+  store::Index* getCache() const;
+
+  void setCache(store::Index* aCache);
+
+  bool cacheResults() const;
+
   PlanIter_t codegen(
         CompilerCB* cb,
         static_context* sctx,
         const QueryLoc& loc,
         std::vector<PlanIter_t>& argv,
         AnnotationHolder& ann) const;
+
+  void
+  computeResultCaching(XQueryDiagnostics*) const;
 };
 
 

=== modified file 'src/runtime/core/fncall_iterator.cpp'
--- src/runtime/core/fncall_iterator.cpp	2011-10-30 00:18:34 +0000
+++ src/runtime/core/fncall_iterator.cpp	2011-11-19 17:32:30 +0000
@@ -48,6 +48,11 @@
 
 #include "util/string_util.h"
 
+#include "store/api/index.h"
+#include "store/api/store.h"
+#include "store/api/iterator_factory.h"
+#include "store/api/temp_seq.h"
+
 #ifdef ZORBA_WITH_DEBUGGER
 #include "debugger/debugger_commons.h"
 
@@ -93,7 +98,8 @@
   thePlanState(NULL),
   thePlanStateSize(0),
   theLocalDCtx(NULL),
-  thePlanOpen(false)
+  thePlanOpen(false),
+  theCache(0)
 {
 }
 
@@ -153,6 +159,7 @@
   {
     thePlan->reset(*thePlanState);
   }
+  theCacheHits.clear();
 }
 
 
@@ -198,6 +205,103 @@
 /*******************************************************************************
 
 ********************************************************************************/
+bool UDFunctionCallIterator::isCached() const
+{
+  return theUDF->cacheResults();
+}
+
+/*******************************************************************************
+
+********************************************************************************/
+void UDFunctionCallIterator::createCache(
+    PlanState& planState,
+    UDFunctionCallIteratorState* state)
+{
+  store::Index_t lIndex = theUDF->getCache();
+  if (!lIndex && theUDF->cacheResults())
+  {
+    const signature& sig = theUDF->getSignature();
+
+    csize numArgs = theChildren.size();
+
+    store::IndexSpecification lSpec;
+    lSpec.theNumKeyColumns = numArgs;
+    lSpec.theKeyTypes.resize(numArgs);
+    lSpec.theCollations.resize(numArgs);
+    lSpec.theIsTemp = true;
+    lSpec.theIsUnique = true;
+    for (csize i = 0; i < numArgs; ++i)
+    {
+      lSpec.theKeyTypes[i] = sig[i]->getBaseBuiltinType()->get_qname().getp();
+    }
+    lIndex = GENV_STORE.createIndex(theUDF->getName(), lSpec, 0);
+    theUDF->setCache(lIndex.getp()); // cache the cache in the function itself
+    state->theCacheHits.reserve(theChildren.size());
+  }
+  state->theCache = lIndex.getp();
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
+bool UDFunctionCallIterator::probeCache(
+    PlanState& planState,
+    UDFunctionCallIteratorState* state,
+    store::Item_t& result,
+    std::vector<store::Item_t>& aKey) const
+{
+  if (!state->theCache)
+    return false;
+
+  store::IndexCondition_t lCond =
+    state->theCache->createCondition(store::IndexCondition::POINT_VALUE);
+
+  std::vector<store::Iterator_t>::iterator lIter 
+    = state->theArgWrappers.begin();
+  for (; lIter != state->theArgWrappers.end(); ++lIter)
+  {
+    store::Iterator_t& argWrapper = (*lIter);
+    store::Item_t lArg;
+    if (argWrapper) // might be 0 if argument is not used
+    {
+      argWrapper->next(lArg); // guaranteed to have exactly one result
+    }
+    aKey.push_back(lArg);
+    lCond->pushItem(lArg);
+  }
+  store::IndexProbeIterator_t lCacheHit = 
+    GENV_STORE.getIteratorFactory()->createIndexProbeIterator(state->theCache);
+  lCacheHit->init(lCond);
+  lCacheHit->open();
+  return lCacheHit->next(result);
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
+void UDFunctionCallIterator::insertCacheEntry(
+  UDFunctionCallIteratorState* state,
+  std::vector<store::Item_t>& aKey,
+  store::Item_t& aValue) const
+{
+  if (state->theCache)
+  {
+    std::auto_ptr<store::IndexKey> k(new store::IndexKey());
+    store::IndexKey* k2 = k.get();
+    k->theItems = aKey;
+    store::Item_t lTmp = aValue; // insert will eventually transfer the Item_t
+    if (!state->theCache->insert(k2, lTmp))
+    {
+      k.release();
+    }
+  }
+}
+
+/*******************************************************************************
+
+********************************************************************************/
 void UDFunctionCallIterator::openImpl(PlanState& planState, uint32_t& offset)
 {
   UDFunctionCallIteratorState* state;
@@ -229,6 +333,11 @@
   // the plan state (but not the state block) and dynamic context.
   state->open(planState, theUDF);
 
+  // if the results of the function should be cached (prereq: atomic in and out)
+  // this functions stores an index in the dynamic context that contains
+  // the cached results. The name of the index is the name of the function.
+  createCache(planState, state);
+
   // Create a wrapper over each subplan that computes an argument expr, if the
   // associated param is actually used anywhere in the function body.
   csize numArgs = theChildren.size();
@@ -301,6 +410,9 @@
 {
   try
   {
+    std::vector<store::Item_t> lKey;
+    bool lCacheHit;
+
     UDFunctionCallIteratorState* state;
     DEFAULT_STACK_INIT(UDFunctionCallIteratorState, state, planState);
 
@@ -314,19 +426,29 @@
       state->thePlanOpen = true;
     }
 
-    // Bind the args.
+    // check if there is a cache and the result is already in the cache
+    lCacheHit = probeCache(planState, state, result, lKey);
+
+    // if not in the cache, we bind the arguments to the function
+    if (!lCacheHit)
     {
       const std::vector<ArgVarRefs>& argsRefs = theUDF->getArgVarsRefs();
-      std::vector<ArgVarRefs>::const_iterator argsRefsIte = argsRefs.begin();
-      std::vector<ArgVarRefs>::const_iterator argsRefsEnd = argsRefs.end();
-
-      std::vector<store::Iterator_t>::iterator argWrapsIte = 
-      state->theArgWrappers.begin();
-
-      for (; argsRefsIte != argsRefsEnd; ++argsRefsIte, ++argWrapsIte)
+      const std::vector<store::Iterator_t>& argWraps = state->theArgWrappers;
+      for (size_t i = 0; i < argsRefs.size(); ++i)
       {
-        store::Iterator_t& argWrapper = (*argWrapsIte);
-        const ArgVarRefs& argVarRefs = (*argsRefsIte);
+        const ArgVarRefs& argVarRefs = argsRefs[i];
+        store::Iterator_t argWrapper;
+        if (state->theCache)
+        {
+          std::vector<store::Item_t> lParam(1, lKey[i]);
+          state->theCacheHits.push_back(GENV_STORE.createTempSeq(lParam));
+          argWrapper = state->theCacheHits.back()->getIterator();
+          argWrapper->open();
+        }
+        else
+        {
+          argWrapper = argWraps[i];
+        }
         ArgVarRefs::const_iterator argVarRefsIte = argVarRefs.begin();
         ArgVarRefs::const_iterator argVarRefsEnd = argVarRefs.end();
 
@@ -343,25 +465,34 @@
       }
     }
 
-#ifdef ZORBA_WITH_DEBUGGER
-    DEBUGGER_PUSH_FRAME;
-#endif
-
-    while (consumeNext(result, state->thePlan, *state->thePlanState))
-    {
-#ifdef ZORBA_WITH_DEBUGGER
-      DEBUGGER_POP_FRAME;
-#endif
-      STACK_PUSH(true, state);
-
-#ifdef ZORBA_WITH_DEBUGGER
-      DEBUGGER_PUSH_FRAME;
-#endif
-    }
-
-#ifdef ZORBA_WITH_DEBUGGER
-    DEBUGGER_POP_FRAME;
-#endif
+    if (lCacheHit)
+    {
+      STACK_PUSH(true, state);
+    }
+    else
+    {
+#ifdef ZORBA_WITH_DEBUGGER
+      DEBUGGER_PUSH_FRAME;
+#endif
+      while (consumeNext(result, state->thePlan, *state->thePlanState))
+      {
+#ifdef ZORBA_WITH_DEBUGGER
+      DEBUGGER_POP_FRAME;
+#endif
+
+      insertCacheEntry(state, lKey, result);
+      STACK_PUSH(true, state);
+
+#ifdef ZORBA_WITH_DEBUGGER
+      DEBUGGER_PUSH_FRAME;
+#endif
+      }
+
+#ifdef ZORBA_WITH_DEBUGGER
+      DEBUGGER_POP_FRAME;
+#endif
+
+    }
 
     STACK_END(state);
 

=== modified file 'src/runtime/core/fncall_iterator.h'
--- src/runtime/core/fncall_iterator.h	2011-10-30 00:18:34 +0000
+++ src/runtime/core/fncall_iterator.h	2011-11-19 17:32:30 +0000
@@ -69,6 +69,19 @@
   the body. So, it is never the case that the arg expr will have more than one 
   consumers, and as a result we can bind all those V references to the same arg
   wrapper.
+
+  theCache:
+  ---------
+  Is an Index which is set in the state if caching for the invoked function
+  should be done. The cache is owned by the UDF itself and shared across
+  all function invocations.
+
+  theCacheHits:
+  -------------
+  If caching is used, this vector contains the results of all arguments
+  of the function evaluation. It's used to bind the variables if the
+  cache didn't give a result in order to avoid duplicate evaluation of
+  the arguments.
 ********************************************************************************/
 class UDFunctionCallIteratorState : public PlanIteratorState 
 {
@@ -79,6 +92,8 @@
   dynamic_context              * theLocalDCtx;
   bool                           thePlanOpen;
   std::vector<store::Iterator_t> theArgWrappers;
+  store::Index                 * theCache;
+  std::vector<store::TempSeq_t>  theCacheHits;
 
   UDFunctionCallIteratorState();
 
@@ -130,6 +145,8 @@
 
   void setDynamic() { theIsDynamic = true; }
 
+  bool isCached() const;
+
   void accept(PlanIterVisitor& v) const;
 
   void openImpl(PlanState& planState, uint32_t& offset);
@@ -139,6 +156,22 @@
   void closeImpl(PlanState& planState);
 
   bool nextImpl(store::Item_t& result, PlanState& planState) const;
+
+protected:
+  void createCache(
+    PlanState& planState,
+    UDFunctionCallIteratorState* state);
+
+  bool probeCache(
+    PlanState& planState,
+    UDFunctionCallIteratorState* state,
+    store::Item_t& result,
+    std::vector<store::Item_t>& aKey) const;
+
+  void insertCacheEntry(
+    UDFunctionCallIteratorState* state,
+    std::vector<store::Item_t>& aKey,
+    store::Item_t& aValue) const;
 };
 
 

=== modified file 'src/runtime/visitors/printer_visitor_impl.cpp'
--- src/runtime/visitors/printer_visitor_impl.cpp	2011-10-11 01:05:23 +0000
+++ src/runtime/visitors/printer_visitor_impl.cpp	2011-11-19 17:32:30 +0000
@@ -1209,7 +1209,23 @@
 
 #undef TYPED_VAL_CMP
 
-  PRINTER_VISITOR_DEFINITION (UDFunctionCallIterator)
+  void PrinterVisitor::beginVisit ( const UDFunctionCallIterator& a )
+  {
+    thePrinter.startBeginVisit("UDFunctionCallIterator", ++theId);
+    printCommons(  &a, theId );
+    if (a.isCached())
+    {
+      thePrinter.addAttribute("cached", "true");
+    }
+    thePrinter.endBeginVisit( theId);
+  }
+
+  void PrinterVisitor::endVisit ( const UDFunctionCallIterator& )
+  {
+    thePrinter.startEndVisit();
+    thePrinter.endEndVisit();
+  }
+
   PRINTER_VISITOR_DEFINITION (ExtFunctionCallIterator)
   PRINTER_VISITOR_DEFINITION (FnBooleanIterator)
   PRINTER_VISITOR_DEFINITION (OrIterator)

=== modified file 'src/store/api/index.h'
--- src/store/api/index.h	2011-10-11 12:11:48 +0000
+++ src/store/api/index.h	2011-11-19 17:32:30 +0000
@@ -415,6 +415,18 @@
    * Returns all keys stored in this index
    */
   virtual KeyIterator_t keys() const = 0;
+
+  /**
+   * Insert the given item in the value set of the given key. If the key is not
+   * in the index already, then the key itself is inserted as well. Return true
+   * if the key was already in the index, false otherwise
+   * The index wil take the ownership of the key if it was not already in the
+   * index.
+   *
+   * @error ZDDY0035 if a key with more than one item is inserted into
+   *  a general index
+   */
+  virtual bool insert(store::IndexKey*& key, store::Item_t& item) = 0;
 };
 
 

=== modified file 'src/store/naive/simple_index_general.cpp'
--- src/store/naive/simple_index_general.cpp	2011-11-15 18:48:54 +0000
+++ src/store/naive/simple_index_general.cpp	2011-11-19 17:32:30 +0000
@@ -236,6 +236,20 @@
 /******************************************************************************
 
 *******************************************************************************/
+bool GeneralIndex::insert(store::IndexKey*& key, store::Item_t& value)
+{
+  if (key->size() != 1)
+  {
+    RAISE_ERROR_NO_LOC(zerr::ZDDY0035_INDEX_GENERAL_INSERT,
+    ERROR_PARAMS(getName()->getStringValue()));
+  }
+  return insert((*key)[0], value);
+}
+
+
+/******************************************************************************
+
+*******************************************************************************/
 bool GeneralIndex::insert(store::Item_t& key, store::Item_t& node)
 {
   bool lossy = false;

=== modified file 'src/store/naive/simple_index_general.h'
--- src/store/naive/simple_index_general.h	2011-11-15 18:48:54 +0000
+++ src/store/naive/simple_index_general.h	2011-11-19 17:32:30 +0000
@@ -174,6 +174,8 @@
 
   bool insert(store::Item_t& key, store::Item_t& node);
 
+  bool insert(store::IndexKey*& key, store::Item_t& value);
+
   virtual bool remove(const store::Item_t& key, store::Item_t& item, bool all) = 0;
 };
 

=== modified file 'src/store/naive/simple_store.cpp'
--- src/store/naive/simple_store.cpp	2011-11-02 17:19:09 +0000
+++ src/store/naive/simple_store.cpp	2011-11-19 17:32:30 +0000
@@ -555,6 +555,9 @@
     store::Iterator* aSourceIter,
     ulong aNumColumns)
 {
+  if (!aSourceIter)
+    return;
+
   store::Item_t domainItem;
   store::IndexKey* key = NULL;
 

=== added file 'test/rbkt/ExpCompilerResults/IterPlan/zorba/udf/udf-fib-rec.iter'
--- test/rbkt/ExpCompilerResults/IterPlan/zorba/udf/udf-fib-rec.iter	1970-01-01 00:00:00 +0000
+++ test/rbkt/ExpCompilerResults/IterPlan/zorba/udf/udf-fib-rec.iter	2011-11-19 17:32:30 +0000
@@ -0,0 +1,42 @@
+Iterator tree for main query:
+<UDFunctionCallIterator cached="true">
+  <SingletonIterator value="xs:integer(100)"/>
+</UDFunctionCallIterator>
+
+Iterator tree for local:fib:
+<flwor::FLWORIterator>
+  <ForVariable name="n">
+    <LetVarIterator varname="n"/>
+  </ForVariable>
+  <ReturnClause>
+    <IfThenElseIterator>
+      <TypedValueCompareIterator_INTEGER>
+        <ForVarIterator varname="n"/>
+        <SingletonIterator value="xs:integer(0)"/>
+      </TypedValueCompareIterator_INTEGER>
+      <SingletonIterator value="xs:integer(0)"/>
+      <IfThenElseIterator>
+        <TypedValueCompareIterator_INTEGER>
+          <ForVarIterator varname="n"/>
+          <SingletonIterator value="xs:integer(1)"/>
+        </TypedValueCompareIterator_INTEGER>
+        <SingletonIterator value="xs:integer(1)"/>
+        <SpecificNumArithIterator_AddOperation_INTEGER>
+          <UDFunctionCallIterator cached="true">
+            <SpecificNumArithIterator_SubtractOperation_INTEGER>
+              <ForVarIterator varname="n"/>
+              <SingletonIterator value="xs:integer(1)"/>
+            </SpecificNumArithIterator_SubtractOperation_INTEGER>
+          </UDFunctionCallIterator>
+          <UDFunctionCallIterator cached="true">
+            <SpecificNumArithIterator_SubtractOperation_INTEGER>
+              <ForVarIterator varname="n"/>
+              <SingletonIterator value="xs:integer(2)"/>
+            </SpecificNumArithIterator_SubtractOperation_INTEGER>
+          </UDFunctionCallIterator>
+        </SpecificNumArithIterator_AddOperation_INTEGER>
+      </IfThenElseIterator>
+    </IfThenElseIterator>
+  </ReturnClause>
+</flwor::FLWORIterator>
+

=== added file 'test/rbkt/ExpQueryResults/zorba/udf/udf-fib-rec.xml.res'
--- test/rbkt/ExpQueryResults/zorba/udf/udf-fib-rec.xml.res	1970-01-01 00:00:00 +0000
+++ test/rbkt/ExpQueryResults/zorba/udf/udf-fib-rec.xml.res	2011-11-19 17:32:30 +0000
@@ -0,0 +1,1 @@
+3736710778780434371

=== added file 'test/rbkt/Queries/zorba/udf/udf-fib-rec.xq'
--- test/rbkt/Queries/zorba/udf/udf-fib-rec.xq	1970-01-01 00:00:00 +0000
+++ test/rbkt/Queries/zorba/udf/udf-fib-rec.xq	2011-11-19 17:32:30 +0000
@@ -0,0 +1,8 @@
+declare function local:fib($n as xs:integer) as xs:integer
+{
+  if ($n eq 0) then 0 
+  else if ($n eq 1) then 1 
+  else local:fib($n - 1) + local:fib($n - 2)
+};
+
+local:fib(100)