[Bug 5620] fts:FormCombinations is incorrect

           Summary: fts:FormCombinations is incorrect
           Product: XPath / XQuery / XSLT
           Version: Working drafts
          Platform: PC
        OS/Version: Windows XP
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Full Text 1.0
        AssignedTo: jim.melton@acm.org
        ReportedBy: thomas.baby@oracle.com
         QAContact: public-qt-comments@w3.org


The XQuery Full-Text specification uses the function fts:FormCombinations
(shown below) to implement the FTTimes operator:

declare function fts:FormCombinations (
      $sms as element(fts:match)*,
      $times as xs:integer )
   as element(fts:match)*
{
   if ( $times eq 1 ) then $sms
   else if (fn:count($sms) lt $times) then ()
   else if (fn:count($sms) eq $times) then
      <fts:match>{$sms/*}</fts:match>
   else (
      fts:FormCombinations(fn:subsequence($sms, 2), $times),
      for $combination in
         fts:FormCombinations(fn:subsequence($sms, 2), $times - 1)
      return
      <fts:match>
      {
         $sms[1]/*,
         $combination/*
      }
      </fts:match>
   )
};

The implementation of fts:ApplyFTTimesAtLeast simply invokes
fts:FTCombinations, which suggests that the above function implements the "at
least $times" semantic.

declare function fts:ApplyFTTimesAtLeast (
      $allMatches as element(fts:allMatches),
      $n as xs:integer )
   as element(fts:allMatches)
{
   <fts:allMatches stokenNum="{$allMatches/@stokenNum}">
   {fts:FormCombinations($allMatches/fts:match, $n)}
   </fts:allMatches>
};


However, looking at the body of fts:FormCombinations, the assumption that it
implements the "at least $times" semantic does not appear to be correct. For
example, fts:FTCombinations invoked with a value of 2 for $times produces only
2-way combinations, and it does not produce 3-way combinations, 4-way
combinations, etc. (Step 3 of the example in Section 4.3.3 should have produced
3-way combinations, but it does not.)

Received on Friday, 4 April 2008 10:00:08 UTC