1/*  $Id$
   2
   3    Part of SWI-Prolog
   4
   5    Author:        Jan Wielemaker
   6    E-mail:        wielemak@science.uva.nl
   7    WWW:           http://www.swi-prolog.org
   8    Copyright (C): 1985-2007, University of Amsterdam
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License
  12    as published by the Free Software Foundation; either version 2
  13    of the License, or (at your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public
  21    License along with this library; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23
  24    As a special exception, if you link this library with other files,
  25    compiled with a Free Software compiler, to produce an executable, this
  26    library does not by itself cause the resulting executable to be covered
  27    by the GNU General Public License. This exception does not however
  28    invalidate any other reasons why the executable file might be covered by
  29    the GNU General Public License.
  30*/
  31
  32:- module(rdf_history,
  33	  [ rdfh_transaction/1,		% :Goal
  34	    rdfh_assert/3,		% +S,+P,+O
  35	    rdfh_retractall/3,		% +S,+P,+O
  36	    rdfh_update/3,		% +S[->NS],+P[->NP],+O[->[NO]
  37	    rdfh_db_transaction/3,	% ?DB, +Condition, ?Transaction
  38	    rdfh_triple_transaction/2,	% +Triple, -Transaction
  39	    rdfh_transaction_member/2	% ?Action, +Transaction
  40	  ]).
  41:- use_module(library('http/http_session')).
  42:- use_module(library(lists)).
  43:- use_module(library(record)).
  44:- use_module(library(error)).
  45:- use_module(library(debug)).
  46:- use_module(library('semweb/rdf_persistency')).
  47:- use_module(library('semweb/rdf_db')).
  48
  49
  50/** <module> RDF Persistent store change history
  51
  52This  module  deals  with  accessing  the   journal  files  of  the  RDF
  53persistency layer to get insight in the   provenance  and history of the
  54RDF database. It is designed for   Wiki-like collaborative editing of an
  55RDF graph. We make the following assumptions:
  56
  57 * Users are identified using a URI, typically an OpenID (http://openid.net/)
  58 * Triples created by a user are added to a named graph identified by the
  59   URI of the user.
  60 * Changes are grouped using rdf_transaction(Goal, log(Message, User))
  61 * The number that is associated with the named graph of a triple (normally
  62   expressing the line number in the source) is used to store the time-stamp.
  63   Although this information is redundant (the time stamp is the same as
  64   for the transaction), it allows for binary search through the history
  65   file for the enclosing transaction.
  66
  67@tbd	Cleanup thoughts on delete and update.
  68
  69@author	Jan Wielemaker
  70*/
  71
  72		 /*******************************
  73		 *	   DECLARATIONS		*
  74		 *******************************/
  75
  76:- module_transparent
  77	rdfh_transaction/1.
  78
  79:- rdf_meta
  80	rdfh_assert(r,r,o),
  81	rdfh_retractall(r,r,o),
  82	rdfh_update(t,t,t).
  83
  84:- multifile
  85	rdfh_hook/1.
  86
  87:- record
  88	rdf_transaction(id:integer,
  89			nesting:integer,
  90			time:number,
  91			message,
  92			actions:list,
  93			other_graphs:list).
  94
  95
  96		 /*******************************
  97		 *	   MODIFICATIONS	*
  98		 *******************************/
  99
 100%%	rdfh_transaction(:Goal) is semidet.
 101%
 102%	Run Goal using rdf_transaction/2, using information from the HTTP
 103%	layer to provide OpenID and session-id.
 104
 105rdfh_transaction(Goal) :-
 106	rdfh_user(User),
 107	transaction_context(Context),
 108	rdf_transaction(Goal, log(rdfh([user(User)|Context]), User)).
 109
 110
 111%%	rdfh_assert(+S, +P, +O) is det.
 112%
 113%	Assert a triple, adding current  user   and  time  to the triple
 114%	context.
 115
 116rdfh_assert(S,P,O) :-
 117	(   rdf_active_transaction(log(rdfh(_), User))
 118	->  rdfh_time(Time),
 119	    rdf_assert(S,P,O,User:Time)
 120	;   throw(error(permission_error(assert, triple, rdf(S,P,O)),
 121			context(_, 'No rdfh_transaction/1')))
 122	).
 123
 124
 125%%	rdfh_retractall(+S, +P, +O) is det.
 126%
 127%	Retract triples that  match  {S,P,O}.   Note  that  all matching
 128%	triples are added to the journal, so   we can undo the action as
 129%	well as report on  retracted  triples,   even  if  multiple  are
 130%	retracted at the same time.
 131%	
 132%	One of the problems we are faced   with is that a retract action
 133%	goes into the journal of  the   user  whose triple is retracted,
 134%	which may or may not be the one who performed the action.
 135
 136rdfh_retractall(S,P,O) :-
 137	(   rdf_active_transaction(log(rdfh(_), _User))
 138	->  rdf_retractall(S,P,O)
 139	;   throw(error(permission_error(retract, triple, rdf(S,P,O)),
 140			context(_, 'No rdfh_transaction/1')))
 141	).
 142
 143
 144%%	rdfh_update(+S, +P, +O) is det.
 145%
 146%	More tricky stuff, replacing a triple by another. Typically this
 147%	will be changing the predicate or object. Provenance info should
 148%	move the new triple to the user making the change, surely if the
 149%	object is changed. If the  predicate   is  changed  to a related
 150%	predicate, this actually becomes less obvious.
 151%	
 152%	Current simple-minded approach is  to  turn   an  update  into a
 153%	retract and assert. The S,P,O specifications are either a ground
 154%	value or of the form _Old_ =|->|= _New_. Here is an example:
 155%	
 156%	==
 157%	rdfh_update(Work, Style, wn:oldstyle -> wn:newstyle)
 158%	==
 159
 160rdfh_update(S,P,O) :-
 161	(   rdf_active_transaction(log(rdfh(_), User))
 162	->  update(S,P,O, rdf(RS, RP, RO), rdf(AS, AP, AO)),
 163	    must_be(ground, RS),
 164	    must_be(ground, RP),
 165	    must_be(ground, RO),
 166	    rdfh_time(Time),
 167	    rdf_retractall(RS, RP, RO),
 168	    rdf_assert(AS, AP, AO, User:Time)
 169	;   throw(error(permission_error(retract, triple, rdf(S,P,O)),
 170			context(_, 'No rdfh_transaction/1')))
 171	).
 172
 173update(Ss, Ps, Os, rdf(S0, P0, O0), rdf(S,P,O)) :-
 174	update(Ss, S0, S),
 175	update(Ps, P0, P),
 176	update(Os, O0, O).
 177
 178update(From->To, From, To) :- !.
 179update(Value, Value, Value).
 180
 181
 182%%	transaction_context(-Term) is det.
 183%
 184%	Context to pass with an RDF transaction.   Note that we pass the
 185%	user. We don't need this for simple additions, but we do need it
 186%	to track deletions.
 187
 188transaction_context(Context) :-
 189	(   rdfh_session(Session)
 190	->  Context = [session(Session)]
 191	;   Context = []
 192	).
 193
 194%%	rdfh_session(-Session) is semidet.
 195%
 196%	Session is a (ground) identifier for the current session.
 197
 198rdfh_session(Session) :-
 199	rdfh_hook(session(Session)), !.
 200rdfh_session(Session) :-
 201	catch(http_session_id(Session), _, fail).
 202
 203
 204%%	rdfh_user(-URI) is det.
 205%
 206%	Get user-id of current session.
 207%	
 208%	@tbd	Make hookable, so we can use the SeRQL user/openid hooks
 209
 210rdfh_user(User) :-
 211	rdfh_hook(user(User)), !.
 212rdfh_user(OpenId) :-
 213	http_session_data(openid(OpenId)).
 214
 215%%	rdfh_time(-Time:integer) is det.
 216%
 217%	Get time stamp as integer.  Second resolution is enough, and
 218%	avoids rounding problems associated with floats.
 219
 220rdfh_time(Seconds) :-
 221	get_time(Now),
 222	Seconds is round(Now).
 223
 224
 225		 /*******************************
 226		 *	 EXAMINE HISTORY	*
 227		 *******************************/
 228
 229%%	rdfh_triple_transaction(+Triple:rdf(S,P,O), -Transaction) is nondet.
 230%
 231%	True if the (partial) Triple is modified in Transaction.
 232
 233rdfh_triple_transaction(rdf(S,P,O), Transaction) :-
 234	rdf(S,P,O,DB:Time),
 235	After is Time - 1,
 236	rdfh_db_transaction(DB, after(After), Transaction),
 237	rdfh_transaction_member(assert(S,P,O,Time), Transaction).
 238
 239%%	rdfh_db_transaction(?DB, +Condition, ?Transaction) is nondet.
 240%
 241%	True if Transaction satisfying  Condition   was  executed on DB.
 242%	Condition is one of:
 243%	
 244%	  * true
 245%	  Always true, returns all transactions.
 246%	  * id(Id)
 247%	  Specifies the identifier of the transaction.  Only makes sense
 248%	  if DB is specified as transaction identifiers are local to each
 249%	  DB.
 250%	  * after(Time)
 251%	  True if transaction is executed at or after Time.
 252%	  
 253%	  @tbd	More conditions (e.g. before(Time)).
 254
 255rdfh_db_transaction(DB, true, Transaction) :- !,
 256	rdf_journal_file(DB, Journal),
 257	journal_transaction(Journal, Transaction).
 258rdfh_db_transaction(DB, id(Id), Transaction) :- !,
 259	must_be(atom, DB),
 260	rdf_journal_file(DB, Journal),
 261	open_journal(Journal, Fd),
 262	call_cleanup((seek_journal(Fd, id(Id)),
 263		      read_transaction(Fd, Transaction)),
 264		     close(Fd)).
 265rdfh_db_transaction(DB, Condition, Transaction) :- !,
 266	valid_condition(Condition),
 267	rdf_journal_file(DB, Journal),
 268	open_journal(Journal, Fd),
 269	seek_journal(Fd, Condition),
 270	stream_transaction(Fd, Transaction).
 271
 272valid_condition(Var) :-
 273	var(Var), !,
 274	instantiation_error(Var).
 275valid_condition(after(Time)) :- !,
 276	must_be(number, Time).
 277valid_condition(Cond) :-
 278	type_error(condition, Cond).
 279
 280%%	open_journal(+File, -Stream) is det.
 281%
 282%	Open a journal file.  Journal files are always UTF-8 encoded.
 283
 284open_journal(JournalFile, Fd) :-
 285	open(JournalFile, read, Fd, [encoding(utf8)]).
 286
 287%%	journal_transaction(+JournalFile, ?Transaction) is nondet.
 288%
 289%	True if Transaction is a transaction in JournalFile,
 290
 291journal_transaction(JournalFile, Transaction) :-
 292	open_journal(JournalFile, Fd),
 293	stream_transaction(Fd, Transaction).
 294
 295stream_transaction(JFD, Transaction) :-
 296	call_cleanup(read_transaction(JFD, Transaction), close(JFD)).
 297
 298read_transaction(In, Transaction) :-
 299	repeat,
 300	   read(In, T0),
 301	(   T0 == end_of_file
 302	->  !, fail
 303	;   transaction(T0, In, T),	% transaction/3 is not steadfast
 304	    T = Transaction
 305	).
 306
 307transaction(begin(Id, Nest, Time, Msg), In,
 308	    rdf_transaction(Id, Nest, Time, Msg, Actions, Others)) :- !,
 309	read(In, T2),
 310	read_transaction_actions(T2, Id, In, Actions, Others).
 311transaction(start(_), _, _) :- !, fail.	% Open journal
 312transaction(end(_), _, _) :- !, fail.   % Close journal
 313transaction(Action, _, Action).		% Action outside transaction?
 314
 315read_transaction_actions(end(Id, _, Others), Id, _, [], Others) :- !.
 316read_transaction_actions(end_of_file, _, _, [], []) :- !. % TBD: Incomplete transaction (error)
 317read_transaction_actions(Action, Id, In, Actions, Others) :-
 318	ignore_in_transaction(Action), !,
 319	read(In, T2),
 320	read_transaction_actions(T2, Id, In, Actions, Others).
 321read_transaction_actions(Action, Id, In, [Action|Actions], Others) :-
 322	read(In, T2),
 323	read_transaction_actions(T2, Id, In, Actions, Others).
 324
 325ignore_in_transaction(start(_)).
 326ignore_in_transaction(end(_)).
 327ignore_in_transaction(begin(_,_,_,_)).
 328ignore_in_transaction(end(_,_,_)).
 329
 330
 331%%	seek_journal(+Fd:stream, +Spec) is semidet.
 332%
 333%	See an open journal descriptor to the start of a transaction
 334%	specified by Spec.  Spec is one of:
 335%	
 336%	  * after(Time)
 337%	  First transaction at or after Time.  Fails if there are no
 338%	  transactions after time.
 339%	  * id(Id)
 340%	  Start of transaction labeled with given Id.  Fails if there
 341%	  is no transaction labeled Id.
 342%	
 343%	The implementation relies on the incrementing identifier numbers
 344%	and time-stamps.
 345
 346seek_journal(Fd, Spec) :-
 347	stream_property(Fd, file_name(File)),
 348	size_file(File, Size),
 349	Here is Size//2,
 350	Last = last(-),
 351	(   is_after_spec(Spec)
 352	->  (   bsearch_journal(Fd, 0, Here, Size, Spec, Last)
 353	    ->	true
 354	    ;	arg(1, Last, StartOfTerm),
 355		StartOfTerm \== (-),
 356		seek(Fd, StartOfTerm, bof, _)
 357	    )
 358	;   bsearch_journal(Fd, 0, Here, Size, Spec, Last)
 359	).
 360
 361is_after_spec(after(_Time)).
 362
 363%%	bsearch_journal(+Fd, +Start, +Here, +End, +Spec, !Last) is semidet.
 364%
 365%	Perform a binary search in the journal opened as Fd.
 366
 367bsearch_journal(Fd, Start, Here, End, Spec, Last) :-
 368	start_of_transaction(Fd, Here, StartOfTerm, Begin), !,
 369	compare_transaction(Spec, Begin, Diff),
 370	(   Diff == (=)
 371	->  seek(Fd, StartOfTerm, bof, _)
 372	;   Diff == (<)
 373	->  NewHere is Start+(Here-Start)//2,
 374	    NewHere < Here,
 375	    nb_setarg(1, Last, StartOfTerm),
 376	    bsearch_journal(Fd, Start, NewHere, Here, Spec, Last)
 377	;   NewHere is StartOfTerm+(End-StartOfTerm)//2,
 378	    NewHere > StartOfTerm,
 379	    bsearch_journal(Fd, StartOfTerm, NewHere, End, Spec, Last)
 380	).
 381bsearch_journal(Fd, Start, Here, _End, Spec, Last) :-
 382	NewHere is Start+(Here-Start)//2,
 383	NewHere	< Here,
 384	bsearch_journal(Fd, Start, NewHere, Here, Spec, Last).
 385
 386compare_transaction(id(Id), begin(Id2,_,_,_), Diff) :- !,
 387	compare(Diff, Id, Id2).
 388compare_transaction(after(Time), begin(_,_,T,_), Diff) :- !,
 389	compare(Diff, Time, T).
 390
 391%%	start_of_transaction(+Fd, +From, -Start, -Term) is semidet.
 392%
 393%	Term is the start  term  of   the  first  transaction after byte
 394%	position From. Fails if no transaction can be found after From.
 395
 396start_of_transaction(Fd, From, Start, Term) :-
 397	seek(Fd, From, bof, _),
 398	skip(Fd, 10),
 399	repeat,
 400	    seek(Fd, 0, current, Start),
 401	    read(Fd, Term),
 402	    (	transaction_start(Term)
 403	    ->	!
 404	    ;	Term == end_of_file
 405	    ->	!, fail
 406	    ;	fail
 407	    ).
 408
 409transaction_start(begin(_Id,_Nest,_Time,_Message)).
 410
 411%%	rdfh_transaction_member(Action, Transaction) is nondet.
 412%
 413%	True if Action is an action in Transaction.
 414
 415rdfh_transaction_member(Action, Transaction) :-
 416	rdf_transaction_actions(Transaction, Actions),
 417	member(Action, Actions).