Coverage report: /development/source/library/org/datagraph/spocq-shard/src/store/rdfcache/matrix-streaming.lisp

Kind	Covered	All	%
expression	0	642	0.0
branch	0	102	0.0

Key

Not instrumented

Conditionalized out

Executed

Not executed

Both branches taken

One branch taken

Neither branch taken

1

;;; -*- Mode: lisp; Syntax: ansi-common-lisp; Base: 10; Package: org.datagraph.spocq.implementation; -*-

2

3

;;; this version changes the match logic to pass the complete set of target graphs

4

;;; to the single match call rather than wrapping the nested matches in an outer loop

5

;;;

6

;;; use rdfcache:match (v/s query) and transactions (v/s repositories)

7

8

(in-package :org.datagraph.spocq.implementation)

9

10

(:documentation "Consolidated BGP matrix-based matching"

11

"Implement bgp matching with results streamed to a paged matrix buffer.

12

In contracted to th emodular implementation, this performs just the

13

iterative nested sip method, but with results emitted through a paged

14

matrix buffer, rather than a page queue.")

15

16

 (defmethod compute-bgp-lambda ((repository rdfcache-consolidated-matrix-repository) body &rest args &key &allow-other-keys)

17

(declare (dynamic-extent args))

18

(apply #'compute-consolidated-matrix-bgp-lambda repository body args))

19

20

;; (defun query-pattern-rewrite-operators (task) (declare (ignore task)) nil)

21

22

23

24

(defun compute-consolidated-matrix-bgp-lambda (agp-repository body &key

25

                                (base-dimensions ())          ; initial solution field variables

26

(projection-dimensions (expression-dimensions body))

27

                                (wildcard-term (repository-wildcard-term agp-repository))

28

                                (default-context-term (repository-default-context-term agp-repository))

29

                                (named-contexts-term (repository-named-contexts-term agp-repository))

30

                                graph    ; if in a graph clause, then either a variable or a literal

31

(dataset-graphs nil)

32

(named-graphs (dataset-named-graphs dataset-graphs))

33

                                (default-graphs (dataset-default-graphs dataset-graphs))

34

(graphs nil)

35

(variables (if (variable-p graph)

36

                                             (cons graph (expression-variables body))

37

(expression-variables body)))

38

(dynamic-variables ())

39

(transaction *transaction*)

40

(trace *compute-bgp-lambda.trace*)

41

(environment nil))

42

   "Generate a matching operator from a BGP for the rdfcache store. The graph matching requirements are

43

described in graph.lisp. They are implemented with the following logic:

44

45

  The graph argument is taken from the agp's graph field. If this bgp is in the scope of a graph clause, that

46

  term noted by the macro-expansion for spocq.a:|graph|. Otherwise, it is an autonomous graph pattern, for

47

  which there is no graph term. The default-graphs and named-graphs terms were either present in the context

48

  query - as specified either in the rquest headers or in the request expression, or were present in the body

49

as spocq.a::|from| and spocq.a::|from-named| forms.

50

51

If the graph is a variable, the bgp applies to named graphs:

52

- if named-graphs is non-null, the match maps the variable over that set, while

53

  - if named-graphs is null, no constraint is applied to the graph variable and it ranges query/next results.

54

If graph is a literal, a variable is introduced, bound to that value at the outset.

55

If graph is null, the bgp applies to 'default' graphs:

56

  - If default-graphs is non-null, a variable is introduced and the match maps it over that set, while

57

  - if default-graphs is null, a variable is introduced, bound to the repository's default graph designator.

58

59

The iteration operator propagates the accumulated bindings over a sequence of core single quad pattern

60

  matches. Each of these starts with a query for which each term is either wild, or a foreign term which

61

  either represents a constant value from the original bgp expression, or carries over a matched term from a

62

  preceeding statement match. The process starts with initial bindings - the graph and/or a solution from an

63

  initial field and augments the bindings as the matches proceed bin binding to the foreign pointers from

64

the successive matches as permitted by a given next.

65

66

This version evolved from the initial rdfcache interface primarily by removing all term structures.

67

As the term identifers are bout retrieved _and_ provided from the query constants, there is no need

68

  to represent the terms' internal structure at the interface to the store. Which means none of the stack definitions

69

for the foreign objects and nothing to substitute in the patterns.

70

  It also eliminates the (broken) mp code, also because it is not clear how to handle thread coordination in

71

a way which does not compromise rdfcache:next iteration rate."

72

73

(declare (ignore environment))

74

(when (assoc 'spocq.a:|quad| body)

75

(error "invalid bpg pattern: ~s" body))

76

;; ensure uniqness

77

(setf variables (remove-duplicates variables :from-end t))

78

(when graphs

79

(warn "graphs ignored ~s." graphs)

80

(log-warn "graphs ignored ~s." graphs))

81

;; use the dimensions provided in the call

82

;; (setf projection-dimensions (expression-dimensions body))

83

(let* (;; if the query had a literal graph term, provide a variable

84

(graph-variable (if (variable-p graph) graph '.graph))

85

;; note if the graph variable is among the initial solutions

86

(initial-solution-graph-variable (find graph base-dimensions))

87

;; indicate whether the graph needs to be set on first query

88

;; (set-graph-variable (and (variable-p graph) (not initial-solution-graph-variable)))

89

          ;; extract just the expressions wto be included in the matching and bindings propagation code

90

(iteration-patterns (remove-if-not #'bgp-pattern-form-p body))

91

(id (second (assoc 'spocq.a::|id| body)))

92

;; extract and consolidate anu declaration clauses

93

          (declarations (reduce #'append (mapcar #'rest (remove 'spocq.a::|declare| body :test-not #'eq :key #'first))))

94

          ;; get the a-list of variables which were inferred to be related through a sameTerm filter constraint

95

;; in order to mirror any binding/setting

96

(equivalents (rest (assoc 'spocq.a::|equivalents| body)))

97

(pattern-count (count 'spocq.a:|triple| iteration-patterns :key #'first))

98

          ;;!!! still builds state for triples with paths even though cursors and terms are handled out-of-line

99

;; adjust bounds to account for per-thread cursors

100

(match-counters (loop for i from 0 below pattern-count collect (gensym "COUNTER")))

101

(temp-match-counters match-counters)

102

(slice-offset (second (assoc 'spocq.a:|slice| body)))

103

(slice-count (third (assoc 'spocq.a:|slice| body)))

104

(projection-variable-count (length projection-dimensions))

105

(equivalent-variables (mapcar #'first equivalents))

106

(collection-variables (difference-dimensions projection-dimensions equivalent-variables))

107

(blank-nodes (expression-blank-nodes iteration-patterns))

108

(blank-node-map (loop for node in blank-nodes

109

collect (cons node (if (spocq:blank-node-constant-p node)

110

                                                   (rdfcache-object-term-number transaction node)

111

                                                   (cons-variable)))))

112

(default-context-term-number (repository-object-term-number agp-repository default-context-term))

113

(named-contexts-term-number (repository-object-term-number agp-repository named-contexts-term))

114

;; track the match nesting; the outer loop only must bind the graph

115

(iteration-level 0)

116

)

117

(declare (ignore declarations))

118

119

(labels ((intern-if-constant (object)

120

(cond ((variable-p object)

121

object)

122

((spocq:blank-node-p object)

123

(or (rest (assoc object blank-node-map))

124

(error "lost a blank-node: ~a" object)))

125

((property-path-p object)

126

(repository-intern-property-path transaction object))

127

(t

128

(rdfcache-object-term-number transaction object))))

129

(intern-predicate (expression)

130

(typecase expression

131

                  (cons (cons (first expression) (mapcar #'intern-predicate (rest expression))))

132

(t (rdfcache-object-term-number transaction expression))))

133

(index-statement-p (statement)

134

(and (consp statement) (member :test statement)))

135

(compute-filter-continuation (triples accumulated-variables)

136

(let* ((form (first triples))

137

(cc (compute-next-continuation (rest triples) accumulated-variables))

138

(test-expression (second form))

139

(test-variables (expression-variables test-expression))

140

                       (test-expression `(handler-case (ebv ,test-expression) (error () nil))))

141

(if test-variables

142

                    (let ((test-aliases (loop for variable in test-variables collect (make-symbol (symbol-name variable)))))

143

`(when ((lambda ,test-aliases

144

                                (symbol-macrolet ,(loop for variable in test-variables

145

                                                        for alias in test-aliases

146

                                                        collect `(,variable (rdfcache-term-number-object transaction ,alias)))

147

                                  (trace-bgp bgp.filter ',test-expression ',test-variables (list ,@test-aliases) (list ,@test-variables))

148

,test-expression))

149

,@test-variables)

150

,cc))

151

`(when ,test-expression ,cc))))

152

(compute-statement-continuation (triples accumulated-variables)

153

(let* ((form (first triples))

154

(dimensions (cons graph-variable (statement-dimensions form)))

155

                       ;; the first match must always use the graph term - either a constant from/from-named iri

156

;; or one of the wild-card, designators default/named/all.

157

                       ;; if wild, then the result matters, but if constant, then the result does not.

158

                       ;; all subsequent iterations use the result from the first match and do not need to rebind

159

(is-first-iteration (= 1 (incf iteration-level)))

160

(last-triple-p (null (assoc 'spocq.a:|triple| (rest triples))))

161

                       ;; set the graph from each result for the outermost iteration only. that means:

162

                       ;; trying w/o this: nb. in contrast to the term-pointer version, which sets the pointer

163

                       ;; once only, the term-id based version must retrieve the id each iteration

164

                       (match-result-arguments (loop ;; for term in (cons graph-variable (statement-terms form))

165

                                                     for term in dimensions

166

                                                     collect (cond ((or (not (variable-p term)) (member term accumulated-variables))

167

                                                                    (gensym "constant"))

168

                                                                   ((and (eq term graph-variable)

169

                                                                         (not is-first-iteration))

170

                                                                    (gensym "constant-graph"))

171

(t

172

                                                                    term))))

173

(uniqued-result-arguments (loop for vars on match-result-arguments

174

                                                       for v in match-result-arguments

175

                                                       collect (if (member v (rest vars))

176

                                                                 (gensym)

177

                                                                 v))))

178

(labels (#+(or) (local-variable-p (v) (member v match-result-arguments))

179

                           #+(or) (wild-variable-p (v) (and (local-variable-p v) (not (eq v graph)))))

180

(let* ((match-pattern (cons graph-variable

181

                                                ;; replace a variable which was not yet returned from a match

182

                                                ;; (loop for term in (statement-terms form) collect (if (wild-variable-p term) wildcard-term term))

183

(statement-terms form)

184

))

185

                           (concrete-match-pattern (let ((graph-term (first match-pattern)))

186

                                                     (cons graph-term (loop for term in (rest match-pattern)

187

                                                                            collect (if (eq term graph-term)

188

                                                                                      `(max 0 ,term) ; cannot pass non-concrete term

189

                                                                                      term)))))

190

                           (match-form `(match-quad-cursor transaction-record ,@concrete-match-pattern *match-target-graph* nil nil))

191

                           (count-form `(count-quad-cursor transaction-record ,@concrete-match-pattern))

192

                           (accumulated-variables (append accumulated-variables (remove-if-not #'symbol-package match-result-arguments)))

193

(body (cond ((property-path-p (third match-pattern))

194

                                        ;; interpret a property path through an out-of-line call to the path matcher

195

                                        (let* ((path-continuation (gensym "PATH-CONTINUATION"))

196

                                               (ignored-variables (remove-if #'symbol-package uniqued-result-arguments))

197

                                               (match-aliases (loop for v in match-result-arguments

198

                                                                    for v-eq = (rassoc v equivalents)

199

                                                                    when v-eq

200

                                                                    collect v-eq

201

                                                                    and do (setf equivalents (remove v-eq equivalents))))

202

                                               (continuation-form (compute-next-continuation (rest triples) accumulated-variables)))

203

204

;; constrain aliased variables

205

                                          (unless (equal uniqued-result-arguments match-result-arguments)

206

(setf continuation-form

207

                                                  `(when (and ,@(loop for v in match-result-arguments

208

                                                                      for u in uniqued-result-arguments

209

                                                                      unless (eq u v)

210

                                                                      collect `(= ,u ,v)))

211

                                                     ,continuation-form)))

212

(when match-aliases

213

                                            #+(or)       ; eliminate alias-rebinding in favor of original dimensions

214

(setf continuation-form

215

                                                  `(let ,(loop for (alias . v) in match-aliases

216

                                                               collect `(,alias ,v))

217

                                                     ,continuation-form)))

218

                                          `(flet ((,path-continuation (,@uniqued-result-arguments)

219

                                                    ,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))

220

                                                    (trace-bgp bgp.pp-matched ,@uniqued-result-arguments)

221

                                                    (unless (task-active-p *query*)

222

                                                      (log-debug "bgp premature completion: ~a" *query*)

223

                                                      (complete-solutions))

224

                                                    ;; when coercing solution graph, restore the match to the initial graphs

225

                                                    ,@(when is-first-iteration

226

                                                        `((note-graph-reference ,(first uniqued-result-arguments))))

227

                                                    ,(if (and slice-offset last-triple-p)

228

                                                       `(when (minusp (decf solution-offset))

229

                                                          ,continuation-form)

230

                                                       continuation-form)))

231

                                             (declare (dynamic-extent #',path-continuation))

232

                                             (trace-bgp bgp.pp-to-match ',concrete-match-pattern)

233

                                             (when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))

234

                                             (match-property-path transaction ,@concrete-match-pattern #',path-continuation))))

235

236

                                       ((extension-operator-p (third match-pattern))

237

                                        ;; interpret a property function through an out-of-line call to funcall-extension

238

                                        (let* ((extension-continuation (gensym "EXTENSION-CONTINUATION"))

239

                                               (ignored-variables (remove-if #'symbol-package uniqued-result-arguments))

240

                                               (match-aliases (loop for v in match-result-arguments

241

                                                                    for v-eq = (rassoc v equivalents)

242

                                                                    when v-eq

243

                                                                    collect v-eq

244

                                                                    and do (setf equivalents (remove v-eq equivalents))))

245

                                               (continuation-form (compute-next-continuation (rest triples) accumulated-variables)))

246

247

;; constrain aliased variables

248

                                          (unless (equal uniqued-result-arguments match-result-arguments)

249

(setf continuation-form

250

                                                  `(when (and ,@(loop for v in match-result-arguments

251

                                                                      for u in uniqued-result-arguments

252

                                                                      unless (eq u v)

253

                                                                      collect `(= ,u ,v)))

254

                                                     ,continuation-form)))

255

(when match-aliases

256

                                            #+(or)       ; eliminate alias-rebinding in favor of original dimensions

257

(setf continuation-form

258

                                                  `(let ,(loop for (alias . v) in match-aliases

259

                                                               collect `(,alias ,v))

260

                                                     ,continuation-form)))

261

                                          `(flet ((,extension-continuation (,@uniqued-result-arguments)

262

                                                    ,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))

263

                                                    (trace-bgp bgp.extension-matched ,@uniqued-result-arguments)

264

                                                    (unless (task-active-p *query*)

265

                                                      (log-debug "bgp premature completion: ~a" *query*)

266

                                                      (complete-solutions))

267

                                                    ;; when coercing solution graph, restore the match to the initial graphs

268

                                                    ,@(when is-first-iteration

269

                                                        `((note-graph-reference ,(first uniqued-result-arguments))))

270

                                                    ,(if (and slice-offset last-triple-p)

271

                                                       `(when (minusp (decf solution-offset))

272

                                                          ,continuation-form)

273

                                                       continuation-form)))

274

                                             (declare (dynamic-extent #',extension-continuation))

275

                                             (trace-bgp bgp.extension ',concrete-match-pattern)

276

                                             (when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))

277

                                             (funcall-extension transaction ,@concrete-match-pattern #',extension-continuation))))

278

279

((index-statement-p form)

280

                                        (let* ((options (member-if #'keywordp form))

281

                                               (test (getf options :test))

282

                                               (index (getf options :index)))

283

                                          (declare (ignore index))       ; held in case one wants to reintroduce the uri

284

                                          (let ((match-index-form `(match-quad-cursor transaction-record ,@concrete-match-pattern target-graph nil

285

                                                                                      ',(intern-predicate test))))

286

;; indexed pattern match

287

                                            `(progn (trace-bgp bgp.cspo-to-match-index ',(nthcdr 3 match-index-form))

288

(incf match-requests)

289

                                               (let ((%match-cursor nil))

290

                                                 (when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))

291

(unwind-protect

292

                                                     (when (setf %match-cursor  ,match-index-form)

293

                                                       (block :cursor-loop

294

                                                         ;; the innermost loop skips past the solution offset

295

                                                         ,@(when (and slice-offset last-triple-p)

296

                                                             `((when (and (plusp solution-offset)

297

                                                                          (plusp (decf solution-offset (dydra-ndk::quad-cursor-skip %match-cursor solution-offset))))

298

                                                                 (return-from :cursor-loop))))

299

(loop

300

                                                           (unless (dydra-ndk::quad-cursor-next %match-cursor) (return))

301

                                                           (incf match-results)

302

                                                           (incf ,(pop temp-match-counters))

303

                                                           (let* (,@(loop for term in match-result-arguments

304

                                                                      for uniqued-term in uniqued-result-arguments

305

                                                                      for accessor in '(dydra-ndk::quad-cursor-graph-id

306

                                                                                         dydra-ndk::quad-cursor-subject-id

307

                                                                                         dydra-ndk::quad-cursor-predicate-id

308

                                                                                         dydra-ndk::quad-cursor-object-id)

309

                                                                      if (symbol-package term) collect `(,uniqued-term (,accessor %match-cursor))))

310

                                                             (declare (ignorable ,@(remove-if-not #'symbol-package uniqued-result-arguments)))

311

                                                             ;; !once! the new bindings are established, compute the next continuation

312

                                                             ,@(when is-first-iteration

313

                                                                  `((note-graph-reference (dydra-ndk::quad-cursor-graph-id %match-cursor))))

314

                                                             ,(let ((form (compute-next-continuation (rest triples) accumulated-variables)))

315

                                                                (if (equal uniqued-result-arguments match-result-arguments)

316

                                                                    form

317

                                                                    `(when (and ,@(loop for v in match-result-arguments

318

                                                                                    for u in uniqued-result-arguments

319

                                                                                    unless (eq u v)

320

                                                                                    collect `(= ,u ,v)))

321

                                                                       ,form)))))))

322

                                                   (when %match-cursor

323

                                                     (dydra-ndk::free-quad-cursor %match-cursor))))))))

324

325

                                       ((or (find-if #'variable-p match-pattern)

326

graph

327

                                            (not (= default-context-term-number rdfcache:*default-context-number*)))

328

                                        ; if variables are in the statement pattern

329

                                        ; or the graph itself is a variable

330

                                        ; or the default graph comrpises the named graphs

331

                                        ; iterate over all matched bindings statement pattern

332

                                        `(progn (trace-bgp bgp.cspo-to-match ',concrete-match-pattern)

333

(incf match-requests)

334

                                                (let ((%match-cursor nil))

335

                                                  (when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))

336

(unwind-protect

337

                                                      (when (setf %match-cursor ,match-form)

338

                                                        (block :cursor-loop

339

                                                          ;; the innermost loop skips past the solution offset

340

                                                          ,@(when (and slice-offset last-triple-p)

341

                                                              `((when (and (plusp solution-offset)

342

                                                                           (plusp (decf solution-offset (dydra-ndk::quad-cursor-skip %match-cursor solution-offset))))

343

                                                                  (return-from :cursor-loop))))

344

                                                          (loop

345

                                                            (unless (dydra-ndk::quad-cursor-next %match-cursor) (return))

346

                                                            (incf match-results)

347

                                                            (incf ,(pop temp-match-counters))

348

                                                            (unless (task-active-p *query*)

349

                                                              (log-debug "bgp premature completion: ~a" *query*)

350

                                                              (complete-solutions))

351

                                                            ;; (rdfcache::print-cursor %match-cursor)

352

                                                            (let* (,@(loop for term in match-result-arguments

353

                                                                       for uniqued-term in uniqued-result-arguments

354

                                                                       for accessor in '(dydra-ndk::quad-cursor-graph-id

355

                                                                                         dydra-ndk::quad-cursor-subject-id

356

                                                                                         dydra-ndk::quad-cursor-predicate-id

357

                                                                                         dydra-ndk::quad-cursor-object-id)

358

                                                                       if (symbol-package term) collect `(,uniqued-term (,accessor %match-cursor))))

359

                                                              (declare (ignorable ,@(remove-if-not #'symbol-package uniqued-result-arguments)))

360

                                                              ;; when coercing solution graph, restore the match to the initial graphs

361

                                                              ,@(when is-first-iteration

362

                                                                  `((note-graph-reference (dydra-ndk::quad-cursor-graph-id %match-cursor))))

363

                                                              ;; note the contributing graph when it is first bound

364

                                                              ;; !once! the new bindings are established, compute the next continuation

365

                                                              ,(let ((form (compute-next-continuation (rest triples) accumulated-variables)))

366

                                                                 (if (equal uniqued-result-arguments match-result-arguments)

367

                                                                     form

368

                                                                     `(when (and ,@(loop for v in match-result-arguments

369

                                                                                     for u in uniqued-result-arguments

370

                                                                                     unless (eq u v)

371

                                                                                     collect `(= ,u ,v)))

372

                                                                        ,form)))))))

373

                                                    (when %match-cursor

374

                                                      (dydra-ndk::free-quad-cursor %match-cursor))))))

375

(t

376

;; just count

377

                                        (let ((continuation-form (compute-next-continuation (rest triples) accumulated-variables)))

378

                                          (unless (equal uniqued-result-arguments match-result-arguments)

379

(setf continuation-form

380

                                                  `(when (and ,@(loop for v in match-result-arguments

381

                                                                      for u in uniqued-result-arguments

382

                                                                      unless (eq u v)

383

                                                                      collect `(= ,u ,v)))

384

                                                     ,continuation-form)))

385

                                          (if (and slice-offset last-triple-p)

386

;; constant slice

387

`(progn (incf match-requests)

388

                                                    (let ((count ,count-form))

389

                                                      (when (and (plusp count)

390

                                                                 (not (plusp (decf solution-offset count))))

391

                                                        (incf match-results)

392

                                                        (incf ,(pop temp-match-counters))

393

                                                        ,continuation-form)))

394

;; constant match

395

`(progn (incf match-requests)

396

                                                    (when (plusp ,count-form)

397

                                                      (incf match-results)

398

                                                      (incf ,(pop temp-match-counters))

399

                                                      ,continuation-form))))))))

400

body))))

401

402

(compute-base-continuation ()

403

;; set the next solution row

404

(let ((collect-form `(collect-solution ,@collection-variables)))

405

(if slice-count

406

`(progn

407

(when (minusp (decf solution-count))

408

(complete-solutions))

409

,collect-form)

410

collect-form)))

411

412

(compute-next-continuation (triples accumulated-variables)

413

(if triples

414

(let* ((form (first triples))) ; (triple ?s ?p ?o)

415

(ecase (first form)

416

(spocq.a:|triple|

417

;; compule a triple/quad into a query/next continuation

418

(compute-statement-continuation triples accumulated-variables))

419

(spocq.a:|filter|

420

                       ;; compile a filter into a constraint on the solutions which pass through it

421

(compute-filter-continuation triples accumulated-variables))))

422

(compute-base-continuation))))

423

424

(setf iteration-patterns (loop for (tag . spo) in iteration-patterns

425

collect (ecase tag

426

(spocq.a:|triple|

427

                                                 (destructuring-bind (s p o &rest args) spo

428

                                                   `(,tag ,(intern-if-constant s)

429

                                                          ,(if (extension-operator-p p)

430

431

                                                             (intern-if-constant p))

432

                                                          ,(intern-if-constant o)

433

                                                          ,@args)))

434

(spocq.a:|filter|

435

(cons tag spo)))))

436

(setf default-graphs (mapcar #'intern-if-constant default-graphs))

437

(setf named-graphs (mapcar #'intern-if-constant named-graphs))

438

(when (and (null default-graphs) (null named-graphs))

439

;; compose the "default dataset"

440

(setf default-graphs (list default-context-term-number)

441

named-graphs (list named-contexts-term-number)))

442

(when (some (complement #'plusp) named-graphs)

443

;; permit a singleton abstract graph only

444

(assert (null (rest named-graphs)) ()

445

"Invalid wildcard dataset named graphs specification: ~a." named-graphs)

446

(setf named-graphs (first named-graphs)))

447

(when (some (complement #'plusp) default-graphs)

448

(assert (null (rest default-graphs)) ()

449

"Invalid wildcard dataset default graph specification: ~a." default-graphs)

450

(setf default-graphs (first default-graphs)))

451

       (setf equivalents (loop for (var . value-or-var) in equivalents collect (cons var (intern-if-constant value-or-var))))

452

453

;; allow for just the graph as a variable for literal bgp patterns?

454

(when (variable-p graph)

455

(setf projection-dimensions (union-dimensions (list graph) projection-dimensions))

456

(setf projection-variable-count (length projection-dimensions)))

457

       (let* (;; the interface operator accepts the repository, and optionally an initial spo solution field, and/or a graph sequence

458

              ;; this wraps an operator which iterates outer over the spo field to bind the starting values for those variables

459

              ;; for each pass and then iterates secondarily over the graph field to perform the pattern matches.

460

;;

461

              ;; the top-level match form starts with all patterns, _no_ bound variables, and the cursor lists

462

              ;; corresponding to the patterns. not even the solution variables are bound initially, as they may themselves

463

;; start out as wild cards.

464

#+(or) ;; the initial call no longer includes constant terms

465

(base-bindings (if (or graphs (not graph))

466

                               (union-dimensions (list graph-variable) base-dimensions)

467

base-dimensions))

468

(base-bindings base-dimensions)

469

(initial-bindings (union-dimensions base-bindings dynamic-variables))

470

;; this cannot work in this way, as it causes all variables to

471

;; be handled as if they are pre-bound, with the consequence, that

472

;; they are matched, but never extractedd from the cursor...

473

;; (initial-bindings (union-dimensions base-bindings variables))

474

(match-invocation-form

475

;; the effective process depends on a combination of :

476

;;

477

;; - the query graph term: null, variable, constant, abstract

478

;; - the dataset default graphs: null, constant, singleton abstract

479

;; normalized above to reflect the default v/s declare composition

480

;; - the dataset named graphs: null, constant, singleton abstract

481

;; normalized above to reflect the default v/s declare composition

482

;; - a propagated solution graph: null, variable

483

;;

484

;; if graph is bound, the bgp is in a graph clause

485

               ;; - if dataset.named-graphs are supplied : they provide the argument for the initial

486

;; match and the result serves for successive, nested calls

487

;; - allow for propagation to be constrained by the dataset

488

;; - allow for - and constrain, a constant graph

489

;; - no dataset.named-graphs

490

;; no match is possible

491

;; no graph indicates the bgp is outside the scope of a graph clause

492

;; - if dataset.default-graphs are supplied : match them the first time _and_

493

               ;;   also for subsequent matches, but substitute the default graph in the result field

494

;; - no dataset.default-graphs

495

;; no match is possible

496

;;

497

               ;; the dataset definition can be a singleton set of a designator for default, named, or all

498

               ;; graphs, in which case the role when matching is the same os that of a concrete graph

499

;;

500

(if graph

501

;; in the scope of a graph clause

502

(cond (named-graphs

503

                          ;; if the dataset definition includes named graphs, permit propgation, constants, or a dynamic binding

504

(cond (initial-solution-graph-variable

505

;; propagate form outside the bgp

506

                                 `(if (eql ,wildcard-term initial-solution-graph-variable)

507

(match-patterns ',named-graphs)

508

                                      (when ,(or (eql named-contexts-term-number named-graphs)

509

                                                 (eql wildcard-term named-graphs)

510

                                                 (if (consp named-graphs)

511

                                                     `(member initial-solution-graph-variable ',named-graphs)

512

                                                     `(eql initial-solution-graph-variable ,named-graphs)))

513

                                          (match-patterns initial-solution-graph-variable))))

514

((variable-p graph)

515

`(if (not (eql ,graph ,wildcard-term))

516

                                      (when ,(or (eql named-contexts-term-number named-graphs)

517

                                                 (eql wildcard-term named-graphs)

518

                                                 (if (consp named-graphs)

519

                                                     `(member ,graph ',named-graphs)

520

                                                     `(eql ,graph ,named-graphs)))

521

(match-patterns ,graph))

522

(match-patterns ',named-graphs))

523

;; bind aa request argument or match as wild

524

#+(or)

525

`(let ((argument (query-binding-value ',graph)))

526

(if (integerp argument)

527

                                        ;; execute with a request parameter if the dataset graphs permit

528

                                        (when ,(or (eql named-contexts-term-number named-graphs)

529

                                                   (eql wildcard-term named-graphs)

530

                                                   (if (consp named-graphs)

531

                                                       `(member argument ',named-graphs)

532

                                                       `(eql argument ,named-graphs)))

533

(match-patterns argument))

534

                                        ;; otherwise, start the match unbound

535

(match-patterns ',named-graphs))))

536

((iri-p graph)

537

(setf graph (intern-if-constant graph))

538

                                 ;; match concrete literal or abstract (named, all)

539

                                 (when (or (eql named-contexts-term-number named-graphs)

540

(eql wildcard-term named-graphs)

541

(eql graph named-graphs)

542

                                           (and (consp named-graphs) (member graph named-graphs)))

543

`(match-patterns ,graph)))

544

(t

545

(error "Invalid graph term: ~s." graph))))

546

(t

547

                          ;; if the dataset includes no named graph, nothing can match

548

nil))

549

(cond (default-graphs

550

                             ;; iff merging into the default graph, the match result must be coerced

551

`(match-patterns ',default-graphs ,default-context-term-number))

552

(t

553

nil))))

554

(triple-matching-form (compute-next-continuation iteration-patterns initial-bindings)))

555

556

(when trace

557

           (format *trace-output* "~&*compute-bgp-lambda.trace*~%body ~s~%graph ~s~%named ~s~%default ~s~%initial-solution-graph-variable ~s~%graph-variable ~s"

558

                   body graph named-graphs default-graphs initial-solution-graph-variable graph-variable))

559

         ;; the actual query operator takes one of two forms. iff base dimensions are included, it is

560

         ;; generated to expect a solution field source, and to iterate the entire operator over the field's solutions.

561

;; without base dimensions, it runs autonomously.

562

         ;; the combination makes it possible to construct query processing both as reduction through bottom-up combination

563

;; and as solution combination, and even as some combination of the two

564

         ;; where evaluation materialized all intermediate solutions, it did not matter that the reduction order agree

565

         ;; with the matching order. the intermediate matching results were cached for delayed use as combination arguments.

566

         ;; where the solution data flows form one operator tot he next, with the intent to limit the space required for

567

         ;; intermediate fields by streaming results, the contradictory evaluation order would still require buffered

568

;; materialization. for example an expression of the form

569

;;

570

;; (join (?a ?b ?c) (join (?b ?c) (?c)))

571

;;

572

;; would reduce with data flow

573

;;

574

;; ((?b ?c) . (?c) . (?a ?b ?c))

575

;;

576

;; but match with data flow

577

;; (?c) -> (?b ?c) -> (?a ?b ?c)

578

;;

579

;; which entail inverted match orders. the question is, how to enable both?

580

581

(let* ((all-bgp-variables

582

;; look for a dynamic binding for all variables in the bgp

583

                 ;; this allows to specify dynamic variables retrospectively, but it may introduce

584

;; an issue related to extracting them from the cursor

585

(set-difference variables base-bindings))

586

(query-lambda

587

`(lambda (bgp-destination ,@(when base-dimensions '(source)))

588

(declare (optimize ,@*field-optimization*))

589

(assert-argument-types bgp-match

590

                                          (bgp-destination (or channel function))

591

                                          ,@(when base-dimensions '((source (or channel function)))))

592

(let* ((repository-id (repository-id *repository*))

593

(revision-id (repository-revision-id *task*))

594

(transaction *transaction*)

595

(transaction-record (transaction-record transaction))

596

                          (*thread-operations* (cons (list 'spocq.a:|bgp| ',body) *thread-operations*))

597

(match-requests 0)

598

(match-results 0)

599

,@(when slice-offset `((solution-offset ,slice-offset)))

600

,@(when slice-count `((solution-count ,slice-count)))

601

(%result-data nil)

602

(result-row 0)

603

(result-count 0)

604

(last-graph-id 0)

605

(graph-ids-read (make-term-id-cache :single-thread t))

606

(*wildcard-identifier* ,wildcard-term)

607

(*default-context-identifier* ,default-context-term-number)

608

,@(loop for var in match-counters collect `(,var 0))

609

                          ;; the original formulation looked for dynamic bindings for all variables

610

                          ;; which were specified as dynamic in the first request but provided to

611

;; be accepted from a propagation source

612

#+(or)

613

                          ,@(loop for var in (intersection (set-difference dynamic-variables base-bindings) variables)

614

                                  collect `(,var (query-binding-term-number ',var)))

615

,@(loop for var in all-bgp-variables

616

                                  collect `(,var (query-binding-term-number ',var)))

617

)

618

                     (declare (ignorable repository-id revision-id transaction-record))         ; if just paths

619

                     (declare (foreign-type (foreign-array ,+matrix-element-type+ (* ,projection-variable-count))

620

%result-data))

621

(declare (type fixnum result-row))

622

                     ,@(when all-bgp-variables ; a variable may have been folded into a constant

623

`((declare (ignorable ,@all-bgp-variables))))

624

(block :bgp-match

625

(labels ((coerce-to-term-id (term-number)

626

(typecase term-number

627

(fixnum term-number)

628

                                    (t (log-warn "bgp match result not a term number: ~s." term-number)

629

+null-term-id+)))

630

(collect-solution ,collection-variables

631

                                  (trace-bgp bgp.match.collect-solution ,@collection-variables)

632

(case *match-target-graph*

633

((nil) )

634

(-1 )

635

                                    (t (log-warn "anomalous match target graph: ~s." *match-target-graph*)))

636

(incf result-count)

637

,(if projection-dimensions

638

                                     `(let ,(loop for (alias . equivalent) in equivalents         ; bind left-over constants

639

                                                  collect (list alias equivalent))

640

(next-solution-location)

641

                                        (locally (declare (ftype (function (t) fixnum) coerce-to-term-id)

642

                                                          (optimize ,@*field-optimization*))

643

                                          (setf ,@(loop for var-index from 0

644

                                                        for variable in projection-dimensions

645

                                                        nconc `((foreign-array-ref %result-data result-row ,var-index)

646

                                                                (coerce-to-term-id ,variable))))))

647

;; for an field without bindings

648

'(next-solution-location)))

649

(next-solution-location ()

650

                                  (setf (values %result-data result-row) (new-field-row bgp-destination)))

651

(complete-solutions ()

652

                                  (trace-bgp bgp.match.complete-solutions result-count)

653

(incf *match-requests* match-requests)

654

(incf *match-responses* match-results)

655

(when (plusp (hash-table-count graph-ids-read))

656

                                    (with-locked-cache ((transaction-read-graph-ids transaction))

657

                                      (loop for id being each hash-key of graph-ids-read

658

                                            do (setf (transaction-graph-id-read transaction id) t))))

659

                                  (log-debug "bgp matches+counts: ~s: requests: ~s, matches: (~s ~s), solutions: ~s"

660

                                             repository-id match-requests match-results (list ,@match-counters) result-count)

661

(complete-field bgp-destination)

662

(incf-stat *solutions-constructed* result-count)

663

(return-from :bgp-match result-count))

664

(put-result (page)

665

                                  (trace-bgp bgp.put bgp-destination ',projection-dimensions page)

666

(put-field-page bgp-destination page)

667

(unless (task-active-p *query*)

668

(complete-field bgp-destination)

669

(return-from :bgp-match result-count)))

670

(note-graph-reference (graph)

671

(unless (eql graph last-graph-id)

672

(setf last-graph-id graph)

673

(setf (gethash graph graph-ids-read) t)))

674

                                (match-quad-cursor (transaction-record context subject predicate object target-graph ordered-p filter)

675

(declare (ignorable filter))

676

                                  (rdfcache::make-quad-cursor transaction-record context subject predicate object

677

                                                              :graph target-graph :ordered ordered-p

678

                                                              ;; :filter filter

679

))

680

                                (count-quad-cursor (transaction-record context subject predicate object)

681

                                  (rdfcache::count-matched-quads transaction-record context subject predicate object))

682

)

683

(trace-bgp bgp.start ',id (task-id *query*)

684

                                    repository-id revision-id ',projection-dimensions)

685

(incf-stat *algebra-operations*)

686

                         (trace-bgp bgp.repository *repository* repository-id revision-id :dataset ',dataset-graphs)

687

                         (if ,(if (find-if #'property-path-p body :key #'third) t 'revision-id)

688

                             ;; unless there are paths present (actually zero-length paths is the issue)

689

                             ;; require an id to perform the query. otherwise there can be no result - skip it

690

(progn

691

                               ; push this logic to the outer-most match call to pass

692

; the entire graph set as the context argument

693

                               ,(let ((iterate-over-graphs `(flet ((match-patterns (effective-dataset-graphs &optional (*match-target-graph* nil)

694

                                                                                                             ,@(when (eq graph-variable '.graph)

695

                                                                                                                 '(&aux (.graph *wildcard-identifier*)))

696

697

                                                                     ;; effective-dataset-graphs is the initial match set

698

                                                                     ;; *match-target-graph*, if bound indicates to coerce the graph term to that

699

                                                                     ;; if the graph is coerced, subsequent matches re-use the original set

700

                                                                     ;; this manages, eg. the case where a set of graphs is 'merged' into the

701

                                                                     ;; default graph, but the result must indicate the default graph only

702

                                                                     (trace-bgp bgp.next-graph effective-dataset-graphs *match-target-graph*)

703

                                                                     (let ((*match-property-path-context* effective-dataset-graphs))

704

                                                                       (when (= *wildcard-identifier* ,graph-variable)

705

                                                                         (setf ,graph-variable effective-dataset-graphs))

706

                                                                       ,triple-matching-form)))

707

                                                              ,match-invocation-form)))

708

(when *compute-bgp-lambda.debug*

709

(pprint iterate-over-graphs))

710

(if base-dimensions

711

`(do-pages (page source)

712

                                                 ,(let ((macros (loop for variable in base-dimensions

713

                                                                  for i from 0

714

                                                                  collect `(,variable (aref page page-index ,i)))))

715

                                                    `(locally (declare (type (simple-array fixnum (* ,(length base-dimensions))) page)

716

                                                                       (optimize ,@*field-optimization*))

717

                                                       (assert (and (typep page '(simple-array fixnum))

718

                                                                    (= (array-dimension page 1) ,(length base-dimensions)))

719

()

720

                                                               "Invalid propagated page: ~s" page)

721

                                                       (trace-data bgp-match.dequeue bgp-destination ',base-dimensions page (term-value-field page))

722

                                                       (loop for page-index from 0 below (array-dimension page 0)

723

                                                         do (symbol-macrolet ,macros

724

                                                                             ,iterate-over-graphs)))))

725

iterate-over-graphs))

726

(trace-bgp bgp.complete-after-graph-iteration)

727

(complete-solutions))

728

(progn (trace-bgp bgp.suppress repository-id)

729

                               (log-debug "suppress query for empty repository: ~a" repository-id)

730

(complete-solutions))))

731

(log-warn "incomplete bgp: ~s." ',id)

732

result-count)))))

733

(log-trace "query [~a] bgp [~a] lambda: ~s"

734

(task-id *query*) id query-lambda)

735

query-lambda)))))