scalable changelog redesign

This patch provides a rewritten changelog system that is designed to run
efficiently on both small and large wikis. The patch includes a plugin to
convert changelogs from the current format. The conversion is
non-destructive and happens automatically. For more information on the new
changelog format see "http://wiki.splitbrain.org/wiki:changelog".

Structure
In short the changelog is now stored in per-page changelog files, with a
recent changes cache. The recent changes cache is kept in
"/data/meta/_dokuwiki.changes" and trimmed daily. The per-page changelogs
are kept in "/data/meta/<ns>/<page_id>.changes" files. To preserve
revision information for revisions stored in the attic, the "*.changes"
files are not removed when their page is deleted. This allows the full
life-cycle of page creation, deletion, and reversion to be tracked.

Format
The changelog line format now uses a general "line type" field in place of
the special "minor" change syntax. There is also an extra field that can
be used to store arbitrary data associated with special line types. The
reverted line type (R) is a good example. There the extra field holds the
revision date used as the source for reverting the page. See the wiki for
the complete syntax description.

Code Notes
The changelog functions have been rewritten to load the whole file only if
it is small. For larger files, the function loads only the relevant
chunk(s). Parsed changelog lines are cached in memory to speed future
function calls.

getRevisionInfo
A binary search is used to locate the chunk expected to contain the
requested revision. The whole chunk is parsed, and adjacent lines are
optimistically cached to speed consecutive calls.

getRevisions
Reads the changelog file backwards (newest first) in chunks until the
requested number of lines have been read. Parsed changelog lines are
cached for subsequent calls to getRevisionInfo. Because revisions are read
from the changelog they are no longer guaranteed to exist in the attic.

(Note: Even with lines of arbitrary length getRevisionInfo and
getRevisions never split changelog lines while reading. This is done by
sliding the "file pointer" forward to the end of a line after each blind
seek.)

isMinor
Removed. To detect a minor edit check the type as follows:
$parsed_logline['type']

darcs-hash:20060830182753-05dcb-1c5ea17f581197a33732a8d11da223d809c03506.gz

10 files changed, 601 insertions, 289 deletions

diff --git a/conf/dokuwiki.php b/conf/dokuwiki.php
index 67d515b29..542431029 100644
--- a/conf/dokuwiki.php
+++ b/conf/dokuwiki.php
@@ -99,6 +99,7 @@ $conf['rss_linkto'] = 'diff';            //what page RSS entries link to:
                                          //  'rev'     - page showing all revisions
                                          //  'current' - most recent revision of page
 $conf['rss_update'] = 5*60;              //Update the RSS feed every n minutes (defaults to 5 minutes)
+$conf['recent_days'] = 7;                //How many days of recent changes to keep. (days)
 
 //Set target to use when creating links - leave empty for same window
 $conf['target']['wiki']      = '';
diff --git a/inc/common.php b/inc/common.php
index 3064c4fda..a0e1e882b 100644
--- a/inc/common.php
+++ b/inc/common.php
@@ -94,16 +94,20 @@ function pageinfo(){
   $info['editable']  = ($info['writable'] && empty($info['lock']));
   $info['lastmod']   = @filemtime($info['filepath']);
 
+  //load page meta data
+  $info['meta'] = p_get_metadata($ID);
+
   //who's the editor
   if($REV){
-    $revinfo = getRevisionInfo($ID,$REV,false);
+    $revinfo = getRevisionInfo($ID, $REV, 1024);
   }else{
-    $revinfo = getRevisionInfo($ID,$info['lastmod'],false);
+    $revinfo = $info['meta']['last_change'];
   }
   $info['ip']     = $revinfo['ip'];
   $info['user']   = $revinfo['user'];
   $info['sum']    = $revinfo['sum'];
-  $info['minor']  = $revinfo['minor'];
+  // See also $INFO['meta']['last_change'] which is the most recent log line for page $ID.
+  // Use $INFO['meta']['last_change']['type']==='e' in place of $info['minor'].
 
   if($revinfo['user']){
     $info['editor'] = $revinfo['user'];
@@ -710,46 +714,53 @@ function dbglog($msg){
 }
 
 /**
- * Add's an entry to the changelog
+ * Add's an entry to the changelog and saves the metadata for the page
  *
  * @author Andreas Gohr <andi@splitbrain.org>
+ * @author Esther Brunner <wikidesign@gmail.com>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
-function addLogEntry($date,$id,$summary='',$minor=false){
-  global $conf;
+function addLogEntry($date, $id, $type='E', $summary='', $extra=''){
+  global $conf, $INFO;
 
-  if(!@is_writable($conf['changelog'])){
-    msg($conf['changelog'].' is not writable!',-1);
-    return;
-  }
+  $id = cleanid($id);
+  $file = wikiFN($id);
+  $created = @filectime($file);
+  $minor = ($type==='e');
+  $wasRemoved = ($type==='D');
 
   if(!$date) $date = time(); //use current time if none supplied
   $remote = $_SERVER['REMOTE_ADDR'];
   $user   = $_SERVER['REMOTE_USER'];
 
-  if($conf['useacl'] && $user && $minor){
-    $summary = '*'.$summary;
-  }else{
-    $summary = ' '.$summary;
+  $logline = array(
+    'date'  => $date,
+    'ip'    => $remote,
+    'type'  => $type,
+    'id'    => $id,
+    'user'  => $user,
+    'sum'   => $summary,
+    'extra' => $extra
+  );
+
+  // update metadata
+  if (!$wasRemoved) {
+    $meta = array();
+    if (!$INFO['exists']){ // newly created
+      $meta['date']['created'] = $created;
+      if ($user) $meta['creator'] = $INFO['userinfo']['name'];
+    } elseif (!$minor) {   // non-minor modification
+      $meta['date']['modified'] = $date;
+      if ($user) $meta['contributor'][$user] = $INFO['userinfo']['name'];
+    }
+    $meta['last_change'] = $logline;
+    p_set_metadata($id, $meta, true);
   }
 
-  $logline = join("\t",array($date,$remote,$id,$user,$summary))."\n";
-  io_saveFile($conf['changelog'],$logline,true);
-}
-
-/**
- * Checks an summary entry if it was a minor edit
- *
- * The summary is cleaned of the marker char
- *
- * @author Andreas Gohr <andi@splitbrain.org>
- */
-function isMinor(&$summary){
-  if(substr($summary,0,1) == '*'){
-    $summary = substr($summary,1);
-    return true;
-  }
-  $summary = trim($summary);
-  return false;
+  // add changelog lines
+  $logline = implode("\t", $logline)."\n";
+  io_saveFile(metaFN($id,'.changes'),$logline,true); //page changelog
+  io_saveFile($conf['changelog'],$logline,true); //global changelog cache
 }
 
 /**
@@ -759,58 +770,39 @@ function isMinor(&$summary){
  *
  * @see getRecents()
  * @author Andreas Gohr <andi@splitbrain.org>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
 function _handleRecent($line,$ns,$flags){
   static $seen  = array();         //caches seen pages and skip them
   if(empty($line)) return false;   //skip empty lines
 
   // split the line into parts
-  list($dt,$ip,$id,$usr,$sum) = explode("\t",$line);
+  $recent = parseChangelogLine($line);
+  if ($recent===false) { return false; }
 
   // skip seen ones
-  if($seen[$id]) return false;
-  $recent = array();
+  if(isset($seen[$recent['id']])) return false;
 
-  // check minors
-  if(isMinor($sum)){
-    // skip minors
-    if($flags & RECENTS_SKIP_MINORS) return false;
-    $recent['minor'] = true;
-  }else{
-    $recent['minor'] = false;
-  }
+  // skip minors
+  if($recent['type']==='e' && ($flags & RECENTS_SKIP_MINORS)) return false;
 
   // remember in seen to skip additional sights
-  $seen[$id] = 1;
+  $seen[$recent['id']] = 1;
 
   // check if it's a hidden page
-  if(isHiddenPage($id)) return false;
+  if(isHiddenPage($recent['id'])) return false;
 
   // filter namespace
-  if (($ns) && (strpos($id,$ns.':') !== 0)) return false;
+  if (($ns) && (strpos($recent['id'],$ns.':') !== 0)) return false;
 
   // exclude subnamespaces
-  if (($flags & RECENTS_SKIP_SUBSPACES) && (getNS($id) != $ns)) return false;
+  if (($flags & RECENTS_SKIP_SUBSPACES) && (getNS($recent['id']) != $ns)) return false;
 
   // check ACL
-  if (auth_quickaclcheck($id) < AUTH_READ) return false;
+  if (auth_quickaclcheck($recent['id']) < AUTH_READ) return false;
 
   // check existance
-  if(!@file_exists(wikiFN($id))){
-    if($flags & RECENTS_SKIP_DELETED){
-      return false;
-    }else{
-      $recent['del'] = true;
-    }
-  }else{
-    $recent['del'] = false;
-  }
-
-  $recent['id']   = $id;
-  $recent['date'] = $dt;
-  $recent['ip']   = $ip;
-  $recent['user'] = $usr;
-  $recent['sum']  = $sum;
+  if((!@file_exists(wikiFN($recent['id']))) && ($flags & RECENTS_SKIP_DELETED)) return false;
 
   return $recent;
 }
@@ -832,7 +824,7 @@ function _handleRecent($line,$ns,$flags){
  * @param string $ns      restrict to given namespace
  * @param bool   $flags   see above
  *
- * @author Andreas Gohr <andi@splitbrain.org>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
 function getRecents($first,$num,$ns='',$flags=0){
   global $conf;
@@ -842,190 +834,245 @@ function getRecents($first,$num,$ns='',$flags=0){
   if(!$num)
     return $recent;
 
-  if(!@is_readable($conf['changelog'])){
-    msg($conf['changelog'].' is not readable',-1);
-    return $recent;
-  }
-
-  $fh  = fopen($conf['changelog'],'r');
-  $buf = '';
-  $csz = 4096;                              //chunksize
-  fseek($fh,0,SEEK_END);                    // jump to the end
-  $pos = ftell($fh);                        // position pointer
-
-  // now read backwards into buffer
-  while($pos > 0){
-    $pos -= $csz;                           // seek to previous chunk...
-    if($pos < 0) {                          // ...or rest of file
-      $csz += $pos;
-      $pos = 0;
+  // read all recent changes. (kept short)
+  $lines = file($conf['changelog']);
+
+  // handle lines
+  for($i = count($lines)-1; $i >= 0; $i--){
+    $rec = _handleRecent($lines[$i], $ns, $flags);
+    if($rec !== false) {
+      if(--$first >= 0) continue; // skip first entries
+      $recent[] = $rec;
+      $count++;
+      // break when we have enough entries
+      if($count >= $num){ break; }
     }
+  }
 
-    fseek($fh,$pos);
-
-    $buf = fread($fh,$csz).$buf;            // prepend to buffer
-
-    $lines = explode("\n",$buf);            // split buffer into lines
-
-    if($pos > 0){
-      $buf = array_shift($lines);           // first one may be still incomplete
-    }
-
-    $cnt = count($lines);
-    if(!$cnt) continue;                     // no lines yet
-
-    // handle lines
-    for($i = $cnt-1; $i >= 0; $i--){
-      $rec = _handleRecent($lines[$i],$ns,$flags);
-      if($rec !== false){
-        if(--$first >= 0) continue;         // skip first entries
-        $recent[] = $rec;
-        $count++;
-
-        // break while when we have enough entries
-        if($count >= $num){
-          $pos = 0; // will break the while loop
-          break;    // will break the for loop
-        }
-      }
-    }
-  }// end of while
-
-  fclose($fh);
   return $recent;
 }
 
 /**
- * Compare the logline $a to the timestamp $b
- * @author Yann Hamon <yann.hamon@mandragor.org>
- * @return integer 0 if the logline has timestamp $b, <0 if the timestam
- *         of $a is greater than $b, >0 else.
- */
-function hasTimestamp($a, $b)
-{
-  if (strpos($a, $b) === 0)
-    return 0;
-  else
-    return strcmp ($a, $b);
-}
-
-/**
- * performs a dichotomic search on an array using
- * a custom compare function
+ * parses a changelog line into it's components
  *
- * @author Yann Hamon <yann.hamon@mandragor.org>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
-function array_dichotomic_search($ar, $value, $compareFunc) {
-  $value = trim($value);
-  if (!$ar || !$value || !$compareFunc) return (null);
-  $len = count($ar);
-
-  $l = 0;
-  $r = $len-1;
-
-  do {
-    $i = floor(($l+$r)/2);
-    if ($compareFunc($ar[$i], $value)<0)
-      $l = $i+1;
-    else
-     $r = $i-1;
-  } while ($compareFunc($ar[$i], $value)!=0 && $l<=$r);
-
-  if ($compareFunc($ar[$i], $value)==0)
-    return $i;
-  else
-    return -1;
+function parseChangelogLine($line) {
+  $tmp = explode("\t", $line);
+    if ($tmp!==false && count($tmp)>1) {
+      $info = array();
+      $info['date']  = $tmp[0]; // unix timestamp
+      $info['ip']    = $tmp[1]; // IPv4 address (127.0.0.1)
+      $info['type']  = $tmp[2]; // log line type
+      $info['id']    = $tmp[3]; // page id
+      $info['user']  = $tmp[4]; // user name
+      $info['sum']   = $tmp[5]; // edit summary (or action reason)
+      $info['extra'] = rtrim($tmp[6], "\n"); // extra data (varies by line type)
+      return $info;
+  } else { return false; }
 }
 
 /**
- * gets additonal informations for a certain pagerevison
- * from the changelog
+ * Get the changelog information for a specific page id
+ * and revision (timestamp). Adjacent changelog lines
+ * are optimistically parsed and cached to speed up
+ * consecutive calls to getRevisionInfo. For large
+ * changelog files, only the chunk containing the
+ * requested changelog line is read.
  *
- * @author Andreas Gohr <andi@splitbrain.org>
- * @author Yann Hamon <yann.hamon@mandragor.org>
  * @author Ben Coburn <btcoburn@silicodon.net>
  */
-function getRevisionInfo($id,$rev,$mem_cache=true){
-  global $conf;
-  global $doku_temporary_revinfo_cache;
-  $cache =& $doku_temporary_revinfo_cache;
-  if(!$rev) return(null);
+function getRevisionInfo($id, $rev, $chunk_size=8192) {
+  global $cache_revinfo;
+  $cache =& $cache_revinfo;
+  if (!isset($cache[$id])) { $cache[$id] = array(); }
+  $rev = max($rev, 0);
 
   // check if it's already in the memory cache
-  if (is_array($cache) && isset($cache[$id]) && isset($cache[$id][$rev])) {
+  if (isset($cache[$id]) && isset($cache[$id][$rev])) {
     return $cache[$id][$rev];
   }
 
-  $info = array();
-  if(!@is_readable($conf['changelog'])){
-    msg($conf['changelog'].' is not readable',-1);
-    return $recent;
-  }
-  $loglines = file($conf['changelog']);
-
-  if (!$mem_cache) {
-    // Search for a line with a matching timestamp
-    $index = array_dichotomic_search($loglines, $rev, 'hasTimestamp');
-    if ($index == -1)
-      return;
-
-    // The following code is necessary when there is more than
-    // one line with one same timestamp
-    $loglines_matching = array();
-    for ($i=$index-1;$i>=0 && hasTimestamp($loglines[$i], $rev) == 0; $i--)
-      $loglines_matching[] = $loglines[$i];
-    $loglines_matching = array_reverse($loglines_matching);
-    $loglines_matching[] =  $loglines[$index];
-    $logsize = count($loglines);
-    for ($i=$index+1;$i<$logsize && hasTimestamp($loglines[$i], $rev) == 0; $i++)
-      $loglines_matching[] = $loglines[$i];
-
-    // pull off the line most recent line with the right id
-    $loglines_matching = array_reverse($loglines_matching); //newest first
-    foreach ($loglines_matching as $logline) {
-      $line = explode("\t", $logline);
-      if ($line[2]==$id) {
-        $info['date']  = $line[0];
-        $info['ip']    = $line[1];
-        $info['user']  = $line[3];
-        $info['sum']   = $line[4];
-        $info['minor'] = isMinor($info['sum']);
-        break;
+  $file = metaFN($id, '.changes');
+  if (!file_exists($file)) { return false; }
+  if (filesize($file)<$chunk_size || $chunk_size==0) {
+    // read whole file
+    $lines = file($file);
+    if ($lines===false) { return false; }
+  } else {
+    // read by chunk
+    $fp = fopen($file, 'rb'); // "file pointer"
+    if ($fp===false) { return false; }
+    $head = 0;
+    fseek($fp, 0, SEEK_END);
+    $tail = ftell($fp);
+    $finger = 0;
+    $finger_rev = 0;
+
+    // find chunk
+    while ($tail-$head>$chunk_size) {
+      $finger = $head+floor(($tail-$head)/2.0);
+      fseek($fp, $finger);
+      fgets($fp); // slip the finger forward to a new line
+      $finger = ftell($fp);
+      $tmp = fgets($fp); // then read at that location
+      $tmp = parseChangelogLine($tmp);
+      $finger_rev = $tmp['date'];
+      if ($finger==$head || $finger==$tail) { break; }
+      if ($finger_rev>$rev) {
+        $tail = $finger;
+      } else {
+        $head = $finger;
       }
     }
+
+    if ($tail-$head<1) {
+      // cound not find chunk, assume requested rev is missing
+      fclose($fp);
+      return false;
+    }
+
+    // read chunk
+    $chunk = '';
+    $chunk_size = max($tail-$head, 0); // found chunk size
+    $got = 0;
+    fseek($fp, $head);
+    while ($got<$chunk_size && !feof($fp)) {
+      $tmp = fread($fp, max($chunk_size-$got, 0));
+      if ($tmp===false) { break; } //error state
+      $got += strlen($tmp);
+      $chunk .= $tmp;
+    }
+    $lines = explode("\n", $chunk);
+    array_pop($lines); // remove trailing newline
+    fclose($fp);
+  }
+
+  // parse and cache changelog lines
+  foreach ($lines as $value) {
+    $tmp = parseChangelogLine($value);
+    if ($tmp!==false) {
+      $cache[$id][$tmp['date']] = $tmp;
+    }
+  }
+  if (!isset($cache[$id][$rev])) { return false; }
+  return $cache[$id][$rev];
+}
+
+/**
+ * Return a list of page revisions numbers
+ * Does not guarantee that the revision exists in the attic,
+ * only that a line with the date exists in the changelog.
+ * By default the current revision is skipped.
+ *
+ * id:    the page of interest
+ * first: skip the first n changelog lines
+ * num:   number of revisions to return
+ *
+ * The current revision is automatically skipped when the page exists.
+ * See $INFO['meta']['last_change'] for the current revision.
+ *
+ * For efficiency, the log lines are parsed and cached for later
+ * calls to getRevisionInfo. Large changelog files are read
+ * backwards in chunks untill the requested number of changelog
+ * lines are recieved.
+ *
+ * @author Ben Coburn <btcoburn@silicodon.net>
+ */
+function getRevisions($id, $first, $num, $chunk_size=8192) {
+  global $cache_revinfo;
+  $cache =& $cache_revinfo;
+  if (!isset($cache[$id])) { $cache[$id] = array(); }
+
+  $revs = array();
+  $lines = array();
+  $count  = 0;
+  $file = metaFN($id, '.changes');
+  $num = max($num, 0);
+  $chunk_size = max($chunk_size, 0);
+  if ($first<0) { $first = 0; }
+  else if (file_exists(wikiFN($id))) {
+     // skip current revision if the page exists
+    $first = max($first+1, 0);
+  }
+
+  if (!file_exists($file)) { return $revs; }
+  if (filesize($file)<$chunk_size || $chunk_size==0) {
+    // read whole file
+    $lines = file($file);
+    if ($lines===false) { return $revs; }
   } else {
-    // load and cache all the lines with the right id
-    if(!is_array($cache)) { $cache = array(); }
-    if (!isset($cache[$id])) { $cache[$id] = array(); }
-    foreach ($loglines as $logline) {
-      $start = strpos($logline, "\t", strpos($logline, "\t")+1)+1;
-      $end = strpos($logline, "\t", $start);
-      if (substr($logline, $start, $end-$start)==$id) {
-        $line = explode("\t", $logline);
-        $info = array();
-        $info['date']  = $line[0];
-        $info['ip']    = $line[1];
-        $info['user']  = $line[3];
-        $info['sum']   = $line[4];
-        $info['minor'] = isMinor($info['sum']);
-        $cache[$id][$info['date']] = $info;
+    // read chunks backwards
+    $fp = fopen($file, 'rb'); // "file pointer"
+    if ($fp===false) { return $revs; }
+    fseek($fp, 0, SEEK_END);
+    $tail = ftell($fp);
+
+    // chunk backwards
+    $finger = max($tail-$chunk_size, 0);
+    while ($count<$num+$first) {
+      fseek($fp, $finger);
+      if ($finger>0) {
+        fgets($fp); // slip the finger forward to a new line
+        $finger = ftell($fp);
+      }
+
+      // read chunk
+      if ($tail<=$finger) { break; }
+      $chunk = '';
+      $read_size = max($tail-$finger, 0); // found chunk size
+      $got = 0;
+      while ($got<$read_size && !feof($fp)) {
+        $tmp = fread($fp, max($read_size-$got, 0));
+        if ($tmp===false) { break; } //error state
+        $got += strlen($tmp);
+        $chunk .= $tmp;
+      }
+      $tmp = explode("\n", $chunk);
+      array_pop($tmp); // remove trailing newline
+
+      // combine with previous chunk
+      $count += count($tmp);
+      $lines = array_merge($tmp, $lines);
+
+      // next chunk
+      if ($finger==0) { break; } // already read all the lines
+      else {
+        $tail = $finger;
+        $finger = max($tail-$chunk_size, 0);
       }
     }
-    $info = $cache[$id][$rev];
+    fclose($fp);
   }
 
-  return $info;
-}
+  // skip parsing extra lines
+  $num = max(min(count($lines)-$first, $num), 0);
+  if      ($first>0 && $num>0)  { $lines = array_slice($lines, max(count($lines)-$first-$num, 0), $num); }
+  else if ($first>0 && $num==0) { $lines = array_slice($lines, 0, max(count($lines)-$first, 0)); }
+  else if ($first==0 && $num>0) { $lines = array_slice($lines, max(count($lines)-$num, 0)); }
 
+  // handle lines in reverse order
+  for ($i = count($lines)-1; $i >= 0; $i--) {
+    $tmp = parseChangelogLine($lines[$i]);
+    if ($tmp!==false) {
+      $cache[$id][$tmp['date']] = $tmp;
+      $revs[] = $tmp['date'];
+    }
+  }
+
+  return $revs;
+}
 
 /**
  * Saves a wikitext by calling io_writeWikiPage
  *
  * @author Andreas Gohr <andi@splitbrain.org>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
 function saveWikiText($id,$text,$summary,$minor=false){
   global $conf;
   global $lang;
+  global $REV;
   // ignore if no changes were made
   if($text == rawWiki($id,'')){
     return;
@@ -1033,14 +1080,19 @@ function saveWikiText($id,$text,$summary,$minor=false){
 
   $file = wikiFN($id);
   $old  = saveOldRevision($id);
+  $wasRemoved = empty($text);
+  $wasCreated = !file_exists($file);
+  $wasReverted = ($REV==true);
 
-  if (empty($text)){
+  if ($wasRemoved){
     // remove empty file
     @unlink($file);
-    // remove any meta info
+    // remove old meta info...
     $mfiles = metaFiles($id);
+    $changelog = metaFN($id, '.changes');
     foreach ($mfiles as $mfile) {
-      if (file_exists($mfile)) @unlink($mfile);
+      // but keep per-page changelog to preserve page history
+      if (file_exists($mfile) && $mfile!==$changelog) { @unlink($mfile); }
     }
     $del = true;
     // autoset summary on deletion
@@ -1051,11 +1103,21 @@ function saveWikiText($id,$text,$summary,$minor=false){
   }else{
     // save file (namespace dir is created in io_writeWikiPage)
     io_writeWikiPage($file, $text, $id);
-    saveMetadata($id, $file, $minor);
     $del = false;
   }
 
-  addLogEntry(@filemtime($file),$id,$summary,$minor);
+  // select changelog line type
+  $extra = '';
+  $type = 'E';
+  if ($wasReverted) {
+    $type = 'R';
+    $extra = $REV;
+  }
+  else if ($wasCreated) { $type = 'C'; }
+  else if ($wasRemoved) { $type = 'D'; }
+  else if ($minor && $conf['useacl'] && $_SERVER['REMOTE_USER']) { $type = 'e'; } //minor edits only for logged in users
+
+  addLogEntry(@filemtime($file), $id, $type, $summary, $extra);
   // send notify mails
   notify($id,'admin',$old,$summary,$minor);
   notify($id,'subscribers',$old,$summary,$minor);
@@ -1067,27 +1129,6 @@ function saveWikiText($id,$text,$summary,$minor=false){
 }
 
 /**
- * saves the metadata for a page
- *
- * @author Esther Brunner <wikidesign@gmail.com>
- */
-function saveMetadata($id, $file, $minor){
-  global $INFO;
-  
-  $user = $_SERVER['REMOTE_USER'];
-  
-  $meta = array();
-  if (!$INFO['exists']){ // newly created
-    $meta['date']['created'] = @filectime($file);
-    if ($user) $meta['creator'] = $INFO['userinfo']['name'];
-  } elseif (!$minor) {   // non-minor modification
-    $meta['date']['modified'] = @filemtime($file);
-    if ($user) $meta['contributor'][$user] = $INFO['userinfo']['name'];
-  }
-  p_set_metadata($id, $meta, true);
-}
-
-/**
  * moves the current version to the attic and returns its
  * revision date
  *
@@ -1178,39 +1219,6 @@ function notify($id,$who,$rev='',$summary='',$minor=false,$replace=array()){
 }
 
 /**
- * Return a list of available page revisons
- *
- * @author Andreas Gohr <andi@splitbrain.org>
- */
-function getRevisions($id){
-  global $conf;
-
-  $id   = cleanID($id);
-  $revd = dirname(wikiFN($id,'foo'));
-  $id   = noNS($id);
-  $id   = utf8_encodeFN($id);
-  $len  = strlen($id);
-  $xlen = 10; // length of timestamp, strlen(time()) would be more correct, 
-              // but i don't expect dokuwiki still running in 287 years ;)
-              // so this will perform better
-
-  $revs = array();
-  if (is_dir($revd) && $dh = opendir($revd)) {
-    while (($file = readdir($dh)) !== false) {
-      if (substr($file,0,$len) === $id) {
-        $time = substr($file,$len+1,$xlen);
-        $time = str_replace('.','FOO',$time); // make sure a dot will make the next test fail
-        $time = (int) $time;
-        if($time) $revs[] = $time;
-      }
-    }
-    closedir($dh);
-  }
-  rsort($revs);
-  return $revs;
-}
-
-/**
  * extracts the query from a google referer
  *
  * @todo   should be more generic and support yahoo et al
@@ -1339,7 +1347,21 @@ function check(){
   if(is_writable($conf['changelog'])){
     msg('Changelog is writable',1);
   }else{
-    msg('Changelog is not writable',-1);
+    if (file_exists($conf['changelog'])) {
+      msg('Changelog is not writable',-1);
+    }
+  }
+
+  if (isset($conf['changelog_old']) && file_exists($conf['changelog_old'])) {
+    msg('Old changelog exists.', 0);
+  }
+
+  if (file_exists($conf['changelog'].'_failed')) {
+    msg('Importing old changelog failed.', -1);
+  } else if (file_exists($conf['changelog'].'_importing')) {
+    msg('Importing old changelog now.', 0);
+  } else if (file_exists($conf['changelog'].'_import_ok')) {
+    msg('Old changelog imported.', 1);
   }
 
   if(is_writable($conf['datadir'])){
diff --git a/inc/html.php b/inc/html.php
index 128cdeb00..4a56072e1 100644
--- a/inc/html.php
+++ b/inc/html.php
@@ -442,19 +442,34 @@ function html_locked(){
  * list old revisions
  *
  * @author Andreas Gohr <andi@splitbrain.org>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
-function html_revisions(){
+function html_revisions($first=0){
   global $ID;
   global $INFO;
   global $conf;
   global $lang;
-  $revisions = getRevisions($ID);
+  /* we need to get one additionally log entry to be able to
+   * decide if this is the last page or is there another one.
+   * see html_recent()
+   */
+  $revisions = getRevisions($ID, $first, $conf['recent']+1);
+  if(count($revisions)==0 && $first!=0){
+    $first=0;
+    $revisions = getRevisions($ID, $first, $conf['recent']+1);;
+  }
+  $hasNext = false;
+  if (count($revisions)>$conf['recent']) {
+    $hasNext = true;
+    array_pop($revisions); // remove extra log entry
+  }
+
   $date = @date($conf['dformat'],$INFO['lastmod']);
 
   print p_locale_xhtml('revisions');
   print '<ul>';
-  if($INFO['exists']){
-    print ($INFO['minor']) ? '<li class="minor">' : '<li>';
+  if($INFO['exists'] && $first==0){
+    print (isset($INFO['meta']) && isset($INFO['meta']['last_change']) && $INFO['meta']['last_change']['type']==='e') ? '<li class="minor">' : '<li>';
     print '<div class="li">';
 
     print $date;
@@ -477,7 +492,7 @@ function html_revisions(){
     $date = date($conf['dformat'],$rev);
     $info = getRevisionInfo($ID,$rev,true);
 
-    print ($info['minor']) ? '<li class="minor">' : '<li>';
+    print ($info['type']==='e') ? '<li class="minor">' : '<li>';
     print '<div class="li">';
     print $date;
 
@@ -507,6 +522,23 @@ function html_revisions(){
     print '</li>';
   }
   print '</ul>';
+
+  print '<div class="pagenav">';
+  $last = $first + $conf['recent'];
+  if ($first > 0) {
+    $first -= $conf['recent'];
+    if ($first < 0) $first = 0;
+    print '<div class="pagenav-prev">';
+    print html_btn('newer','',"p",array('do' => 'revisions', 'first' => $first));
+    print '</div>';
+  }
+  if ($hasNext) {
+    print '<div class="pagenav-next">';
+    print html_btn('older','',"n",array('do' => 'revisions', 'first' => $last));
+    print '</div>';
+  }
+  print '</div>';
+
 }
 
 /**
@@ -514,6 +546,7 @@ function html_revisions(){
  *
  * @author Andreas Gohr <andi@splitbrain.org>
  * @author Matthias Grimm <matthiasgrimm@users.sourceforge.net>
+ * @author Ben Coburn <btcoburn@silicodon.net>
  */
 function html_recent($first=0){
   global $conf;
@@ -526,16 +559,20 @@ function html_recent($first=0){
   $recents = getRecents($first,$conf['recent'] + 1,getNS($ID));
   if(count($recents) == 0 && $first != 0){
     $first=0;
-    $recents = getRecents(0,$conf['recent'] + 1,getNS($ID));
+    $recents = getRecents($first,$conf['recent'] + 1,getNS($ID));
+  }
+  $hasNext = false;
+  if (count($recents)>$conf['recent']) {
+    $hasNext = true;
+    array_pop($recents); // remove extra log entry
   }
-  $cnt = count($recents) <= $conf['recent'] ? count($recents) : $conf['recent'];
 
   print p_locale_xhtml('recent');
   print '<ul>';
 
   foreach($recents as $recent){
     $date = date($conf['dformat'],$recent['date']);
-    print ($recent['minor']) ? '<li class="minor">' : '<li>';
+    print ($recent['type']==='e') ? '<li class="minor">' : '<li>';
     print '<div class="li">';
 
     print $date.' ';
@@ -587,7 +624,7 @@ function html_recent($first=0){
     print html_btn('newer','',"p",array('do' => 'recent', 'first' => $first));
     print '</div>';
   }
-  if ($conf['recent'] < count($recents)) {
+  if ($hasNext) {
     print '<div class="pagenav-next">';
     print html_btn('older','',"n",array('do' => 'recent', 'first' => $last));
     print '</div>';
@@ -782,7 +819,7 @@ function html_diff($text='',$intro=true){
       $r = $REV;
     }else{
       //use last revision if none given
-      $revs = getRevisions($ID);
+      $revs = getRevisions($ID, 0, 1);
       $r = $revs[0];
     }
 
diff --git a/inc/init.php b/inc/init.php
index 01d2f7469..bfa22e001 100644
--- a/inc/init.php
+++ b/inc/init.php
@@ -24,8 +24,8 @@
   else { error_reporting(DOKU_E_LEVEL); }
 
   // init memory caches
-  global $cache_wikifn; $cache_wikifn = array();
-  global $cache_wikifn; $cache_cleanid = array();
+  $cache_wikifn = array();
+  $cache_cleanid = array();
 
   //prepare config array()
   global $conf;
@@ -128,8 +128,7 @@ function init_paths(){
                  'mediadir'  => 'media',
                  'metadir'   => 'meta',
                  'cachedir'  => 'cache',
-                 'lockdir'   => 'locks',
-                 'changelog' => 'changes.log');
+                 'lockdir'   => 'locks');
 
   foreach($paths as $c => $p){
     if(!$conf[$c])   $conf[$c] = $conf['savedir'].'/'.$p;
@@ -139,6 +138,12 @@ function init_paths(){
                                Or maybe you want to <a href=\"install.php\">run the
                                installer</a>?");
   }
+
+  // path to old changelog only needed for upgrading
+  $conf['changelog_old'] = init_path((isset($conf['changelog']))?($conf['changelog']):($conf['savedir'].'/changes.log'));
+  if ($conf['changelog_old']=='') { unset($conf['changelog_old']); }
+  // hardcoded changelog because it is now a cache that lives in meta
+  $conf['changelog'] = $conf['metadir'].'/_dokuwiki.changes';
 }
 
 /**
diff --git a/inc/template.php b/inc/template.php
index f06503043..d30500e94 100644
--- a/inc/template.php
+++ b/inc/template.php
@@ -81,7 +81,8 @@ function tpl_content_core(){
       html_search();
       break;
     case 'revisions':
-      html_revisions();
+      $first = is_numeric($_REQUEST['first']) ? intval($_REQUEST['first']) : 0;
+      html_revisions($first);
       break;
     case 'diff':
       html_diff();
diff --git a/lib/exe/indexer.php b/lib/exe/indexer.php
index 2728e5665..d65707911 100644
--- a/lib/exe/indexer.php
+++ b/lib/exe/indexer.php
@@ -27,7 +27,7 @@ if(@ignore_user_abort()){
 if(!$_REQUEST['debug']) ob_start();
 
 // run one of the jobs
-runIndexer() or metaUpdate() or runSitemapper();
+runIndexer() or metaUpdate() or runSitemapper() or runTrimRecentChanges();
 if($defer) sendGIF();
 
 if(!$_REQUEST['debug']) ob_end_clean();
@@ -36,6 +36,73 @@ exit;
 // --------------------------------------------------------------------
 
 /**
+ * Trims the recent changes cache (or imports the old changelog) as needed.
+ *
+ * @author Ben Coburn <btcoburn@silicodon.net>
+ */
+function runTrimRecentChanges() {
+    global $conf;
+
+    // Import old changelog (if needed)
+    // Uses the imporoldchangelog plugin to upgrade the changelog automaticaly.
+    // FIXME: Remove this from runTrimRecentChanges when it is no longer needed.
+    if (isset($conf['changelog_old']) &&
+        file_exists($conf['changelog_old']) && !file_exists($conf['changelog']) &&
+        !file_exists($conf['changelog'].'_importing') && !file_exists($conf['changelog'].'_tmp')) {
+            $tmp = array(); // no event data
+            trigger_event('TEMPORARY_CHANGELOG_UPGRADE_EVENT', $tmp);
+            return true;
+    }
+
+    // Trim the Recent Changes
+    // Trims the recent changes cache to the last $conf['changes_days'] recent
+    // changes or $conf['recent'] items, which ever is larger.
+    // The trimming is only done once a day.
+    if (file_exists($conf['changelog']) &&
+        (filectime($conf['changelog'])+86400)<time() &&
+        !file_exists($conf['changelog'].'_tmp')) {
+            io_lock($conf['changelog']);
+            $lines = file($conf['changelog']);
+            if (count($lines)<$conf['recent']) {
+                // nothing to trim
+                io_unlock($conf['changelog']);
+                return true;
+            }
+            // trim changelog
+            io_saveFile($conf['changelog'].'_tmp', ''); // presave tmp as 2nd lock
+            $kept = 0;
+            $trim_time = time() - $conf['recent_days']*86400;
+            $out_lines = array();
+            // check lines from newest to oldest
+            for ($i = count($lines)-1; $i >= 0; $i--) {
+                $tmp = parseChangelogLine($lines[$i]);
+                if ($tmp===false) { continue; }
+                if ($tmp['date']>$trim_time || $kept<$conf['recent']) {
+                    array_push($out_lines, implode("\t", $tmp)."\n");
+                    $kept++;
+                } else {
+                    // no more lines worth keeping
+                    break;
+                }
+            }
+            io_saveFile($conf['changelog'].'_tmp', implode('', $out_lines));
+            unlink($conf['changelog']);
+            if (!rename($conf['changelog'].'_tmp', $conf['changelog'])) {
+                // rename failed so try another way...
+                io_unlock($conf['changelog']);
+                io_saveFile($conf['changelog'], implode('', $out_lines));
+                unlink($conf['changelog'].'_tmp');
+            } else {
+                io_unlock($conf['changelog']);
+            }
+            return true;
+    }
+
+    // nothing done
+    return false;
+}
+
+/**
  * Runs the indexer for the current page
  *
  * @author Andreas Gohr <andi@splitbrain.org>
diff --git a/lib/plugins/config/lang/en/lang.php b/lib/plugins/config/lang/en/lang.php
index c2bd5aacf..4c4c713e5 100644
--- a/lib/plugins/config/lang/en/lang.php
+++ b/lib/plugins/config/lang/en/lang.php
@@ -124,6 +124,7 @@ $lang['sitemap']     = 'Generate Google sitemap (days)';
 $lang['rss_type']    = 'XML feed type';
 $lang['rss_linkto']  = 'XML feed links to';
 $lang['rss_update']  = 'XML feed update interval (sec)';
+$lang['recent_days'] = 'How many recent changes to keep (days)';
 
 /* Target options */
 $lang['target____wiki']      = 'Target window for internal links';
diff --git a/lib/plugins/config/settings/config.metadata.php b/lib/plugins/config/settings/config.metadata.php
index 0dd9f1de3..b55c0e930 100644
--- a/lib/plugins/config/settings/config.metadata.php
+++ b/lib/plugins/config/settings/config.metadata.php
@@ -162,6 +162,7 @@ $meta['sitemap']     = array('numeric');
 $meta['rss_type']    = array('multichoice','_choices' => array('rss','rss1','rss2','atom'));
 $meta['rss_linkto']  = array('multichoice','_choices' => array('diff','page','rev','current'));
 $meta['rss_update']  = array('numeric');
+$meta['recent_days'] = array('numeric');
 
 $meta['_network']    = array('fieldset');
 $meta['proxy____host'] = array('string','_pattern' => '#^[a-z0-9\-\.+]+?#i');
diff --git a/lib/plugins/importoldchangelog/action.php b/lib/plugins/importoldchangelog/action.php
new file mode 100644
index 000000000..400ff6a18
--- /dev/null
+++ b/lib/plugins/importoldchangelog/action.php
@@ -0,0 +1,177 @@
+<?php
+// must be run within Dokuwiki
+if(!defined('DOKU_INC')) die();
+
+if(!defined('DOKU_PLUGIN')) define('DOKU_PLUGIN',DOKU_INC.'lib/plugins/');
+require_once(DOKU_PLUGIN.'action.php');
+
+class action_plugin_importoldchangelog extends DokuWiki_Action_Plugin {
+
+	function getInfo(){
+		return array(
+			'author' => 'Ben Coburn',
+			'email'  => 'btcoburn@silicodon.net',
+			'date'   => '2006-08-30',
+			'name'   => 'Import Old Changelog',
+			'desc'   => 'Imports and converts the single file changelog '.
+                        'from the 2006-03-09b release to the new format. '.
+                        'Also reconstructs missing changelog data from  '.
+                        'old revisions kept in the attic.',
+            'url'    => 'http://wiki.splitbrain.org/wiki:changelog'
+			);
+	}
+
+	function register(&$controller) {
+        $controller->register_hook('TEMPORARY_CHANGELOG_UPGRADE_EVENT', 'BEFORE', $this, 'run_import');
+	}
+
+    function importOldLog($line, &$logs) {
+        global $lang;
+        /*
+        // Note: old log line format
+        //$info['date']  = $tmp[0];
+        //$info['ip']    = $tmp[1];
+        //$info['id']    = $tmp[2];
+        //$info['user']  = $tmp[3];
+        //$info['sum']   = $tmp[4];
+        */
+        $oldline = @explode("\t", $line);
+        if ($oldline!==false && count($oldline)>1) {
+            // trim summary
+            $wasMinor = (substr($oldline[4], 0, 1)==='*');
+            $sum = rtrim(substr($oldline[4], 1), "\n");
+            // guess line type
+            $type = 'E';
+            if ($wasMinor) { $type = 'e'; }
+            if ($sum===$lang['created']) { $type = 'C'; }
+            if ($sum===$lang['deleted']) { $type = 'D'; }
+            // build new log line
+            $tmp = array();
+            $tmp['date']  = $oldline[0];
+            $tmp['ip']    = $oldline[1];
+            $tmp['type']  = $type;
+            $tmp['id']    = $oldline[2];
+            $tmp['user']  = $oldline[3];
+            $tmp['sum']   = $sum;
+            $tmp['extra'] = '';
+            // order line by id
+            if (!isset($logs[$tmp['id']])) { $logs[$tmp['id']] = array(); }
+            $logs[$tmp['id']][$tmp['date']] = $tmp;
+        }
+    }
+
+    function importFromAttic(&$logs) {
+        global $conf, $lang;
+        $base = $conf['olddir'];
+        $stack = array('');
+        $context = ''; // namespace
+        while (count($stack)>0){
+            $context = array_pop($stack);
+            $dir = dir($base.'/'.str_replace(':', '/', $context));
+
+            while (($file = $dir->read()) !== false) {
+                if ($file==='.' || $file==='..') { continue; }
+                $matches = array();
+                if (preg_match('/([^.]*)\.([^.]*)\..*/', $file, $matches)===1) {
+                    $id = (($context=='')?'':$context.':').$matches[1];
+                    $date = $matches[2];
+
+                    // check if page & revision are already logged
+                    if (!isset($logs[$id])) { $logs[$id] = array(); }
+                    if (!isset($logs[$id][$date])) {
+                        $tmp = array();
+                        $tmp['date']  = $date;
+                        $tmp['ip']    = '127.0.0.1'; // original ip lost
+                        $tmp['type']  = 'E';
+                        $tmp['id']    = $id;
+                        $tmp['user']  = ''; // original user lost
+                        $tmp['sum']   = '('.$lang['restored'].')'; // original summary lost
+                        $tmp['extra'] = '';
+                        $logs[$id][$date] = $tmp;
+                    }
+
+                } else if (is_dir($dir->path.'/'.$file)) {
+                    array_push($stack, (($context=='')?'':$context.':').$file);
+                }
+
+            }
+
+            $dir->close();
+        }
+
+    }
+
+    function savePerPageChanges($id, &$changes, &$recent, $trim_time) {
+        $out_lines = array();
+        ksort($changes); // ensure correct order of changes from attic
+        foreach ($changes as $tmp) {
+            $line = implode("\t", $tmp)."\n";
+            array_push($out_lines, $line);
+            if ($tmp['date']>$trim_time) {
+                $recent[$tmp['date']] = $line;
+            }
+        }
+        io_saveFile(metaFN($id, '.changes'), implode('', $out_lines));
+    }
+
+    function resetTimer() {
+        // Add 5 minutes to the script execution timer...
+        // This should be much more than needed.
+        set_time_limit(5*60);
+        // Note: Has no effect in safe-mode!
+    }
+
+    function run_import(&$event, $args) {
+        global $conf;
+        register_shutdown_function('importoldchangelog_plugin_shutdown');
+        touch($conf['changelog'].'_importing'); // changelog importing lock
+        io_saveFile($conf['changelog'], ''); // pre-create changelog
+        io_lock($conf['changelog']);  // hold onto the lock
+        // load old changelog
+        $this->resetTimer();
+        $log = array();
+        $oldlog = file($conf['changelog_old']);
+        foreach ($oldlog as $line) {
+            $this->importOldLog($line, $log);
+        }
+        unset($oldlog); // free memory
+        // look in the attic for unlogged revisions
+        $this->resetTimer();
+        $this->importFromAttic($log);
+        // save per-page changelogs
+        $this->resetTimer();
+        $recent = array();
+        $trim_time = time() - $conf['recent_days']*86400;
+        foreach ($log as $id => $page) {
+            $this->savePerPageChanges($id, $page, $recent, $trim_time);
+        }
+        // save recent changes cache
+        $this->resetTimer();
+        ksort($recent); // ensure correct order of recent changes
+        io_unlock($conf['changelog']); // hand off the lock to io_saveFile
+        io_saveFile($conf['changelog'], implode('', $recent));
+        unlink($conf['changelog'].'_importing'); // changelog importing unlock
+    }
+
+}
+
+function importoldchangelog_plugin_shutdown() {
+    global $conf;
+    $path = array();
+    $path['changelog'] = $conf['changelog'];
+    $path['importing'] = $conf['changelog'].'_importing';
+    $path['failed']    = $conf['changelog'].'_failed';
+    $path['import_ok'] = $conf['changelog'].'_import_ok';
+    io_unlock($path['changelog']); // guarantee unlocking
+    if (file_exists($path['importing'])) {
+        // import did not finish
+        rename($path['importing'], $path['failed']) or trigger_error('Importing changelog failed.', E_USER_WARNING);
+        @unlink($path['import_ok']);
+    } else {
+        // import successful
+        touch($path['import_ok']);
+        @unlink($path['failed']);
+    }
+}
+
+
diff --git a/lib/plugins/plugin/admin.php b/lib/plugins/plugin/admin.php
index ef142c4cc..2c47de665 100644
--- a/lib/plugins/plugin/admin.php
+++ b/lib/plugins/plugin/admin.php
@@ -23,7 +23,7 @@ require_once(DOKU_PLUGIN.'admin.php');
 		
 		// plugins that are an integral part of dokuwiki, they shouldn't be disabled or deleted
 		global $plugin_protected;
-		$plugin_protected = array('acl','plugin','config','info','usermanager');
+		$plugin_protected = array('acl','plugin','config','info','usermanager', 'importoldchangelog');
 		
 /**
  * All DokuWiki plugins to extend the admin function