-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathphpinspect-meta.el
396 lines (327 loc) · 16.1 KB
/
phpinspect-meta.el
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
;;; phpinspect-meta.el --- PHP parsing and completion package -*- lexical-binding: t; -*-
;; Copyright (C) 2021-2023 Free Software Foundation, Inc
;; Author: Hugo Thunnissen <[email protected]>
;; Keywords: php, languages, tools, convenience
;; Version: 2.1.0
;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
;; GNU General Public License for more details.
;; You should have received a copy of the GNU General Public License
;; along with this program. If not, see <https://www.gnu.org/licenses/>.
;;; Commentary:
;;
;; IMPLEMENTATION CONTEXT
;;
;; This file contains code for the storing and reading of metadata related to
;; the tokens in a parsed syntax tree.
;;
;; Phpinspect's parser uses basic lists as datastructure for its parsing
;; result. The simplicity of the datastructure makes it performant as the amount
;; of GC's triggered by simple lists is not as large as when using more complex
;; datastructures.
;;
;; A drawback of this simplicity is that attaching additional metadata to the
;; parsed tokens is nontrivial. A list is a list: There is no way to store
;; additional metadata in a separate slot that is not part of its overall
;; members. This is fine when parsing entire files and indexing their
;; contents. Efficiently maintaining the state of code in a buffer, however, is
;; a more involved process. It requires the storage of more metadata than just
;; the parsed tokens.
;;
;; For this reason, phpinspect uses a metadata tree for live buffers. The
;; metadata tree can be interacted with through functions prefixed with
;; "phpinspect-meta". It is an n-ary tree that can be navigated and searched
;; through using the start position of parsed tokens. Each metadata object
;; stores its direct children in a binary search tree (see phpinspect-splayt.el).
;;
;; The metadata tree makes it easy to dig down in a buffer's syntax tree and
;; determine the context from which a user is interacting with the PHP code in
;; it.
;;
;;; Code:
(require 'phpinspect-splayt)
(eval-and-compile
(defvar phpinspect-meta--point-offset-base nil
"This variable overrides `phpinspect-meta-start'. Normally,
metadata objects derive their start position relative to their
parents. This is at some performance cost because the start
position is re-calculated each time it is accessed.
There are scenarios, most notably when parsing incrementally,
where the start position of the token is already known while
interacting with the metadata object. In such cases this variable
can be set to override the start position, preventing any
additional calculations.
Note: Use this sparingly in scenarios where performance is of
significant importance. The code that uses this will be harder to
maintain. It requires a lot of mental tracing to know when to
set/unset this variable."))
(define-inline phpinspect-make-meta
(parent start end whitespace-before token &optional children parent-offset)
"Create a metadata object for TOKEN."
(inline-letevals (start end)
(inline-quote (list 'meta ,parent ,start ,end ,whitespace-before ,token
(or ,children (phpinspect-make-splayt)) ,parent-offset))))
(define-inline phpinspect-meta-p (meta)
(inline-quote (eq 'meta (car-safe ,meta))))
(define-inline phpinspect-meta-parent (meta)
(inline-quote (cadr ,meta)))
(define-inline phpinspect-meta-children (meta)
(inline-quote (car (nthcdr 6 ,meta))))
(define-inline phpinspect-meta-parent-offset (meta)
(inline-quote (car (nthcdr 7 ,meta))))
(define-inline phpinspect-meta-token (meta)
(inline-quote (car (nthcdr 5 ,meta))))
(define-inline phpinspect-meta-absolute-end (meta)
(inline-quote (cadddr ,meta)))
(define-inline phpinspect-meta-whitespace-before (meta)
(inline-quote (car (cddddr ,meta))))
(define-inline phpinspect-meta-parent-start (meta)
"Calculate parent start position iteratively based on parent offsets."
(inline-letevals (meta)
(inline-quote
(let ((start (or (phpinspect-meta-parent-offset ,meta) 0))
(current ,meta))
(while (phpinspect-meta-parent current)
(setq current (phpinspect-meta-parent current)
start (+ start (or (phpinspect-meta-parent-offset current) 0))))
(+ (phpinspect-meta-absolute-start current) start)))))
(define-inline phpinspect-meta--start (meta)
"Calculate the start position of META."
(inline-letevals (meta)
(inline-quote
(if (phpinspect-meta-parent ,meta)
(+ (phpinspect-meta-parent-start (phpinspect-meta-parent ,meta))
(phpinspect-meta-parent-offset ,meta))
(phpinspect-meta-absolute-start ,meta)))))
(define-inline phpinspect-meta-start (meta)
"Start position of META.
Either calculates relative to parent or returns
`phpinspect-meta--point-offset-base' when that variable is set."
(inline-quote
(or phpinspect-meta--point-offset-base (phpinspect-meta--start ,meta))))
(define-inline phpinspect-meta-width (meta)
(inline-letevals (meta)
(inline-quote
(- (phpinspect-meta-absolute-end ,meta) (phpinspect-meta-absolute-start ,meta)))))
(define-inline phpinspect-meta-end (meta)
(inline-letevals (meta)
(inline-quote
(+ (phpinspect-meta-start ,meta) (phpinspect-meta-width ,meta)))))
(defun phpinspect-meta-find-root (meta)
"Find the root node of META's tree."
(while (phpinspect-meta-parent meta)
(setq meta (phpinspect-meta-parent meta)))
meta)
(defun phpinspect-meta-sort-width (meta1 meta2)
(< (phpinspect-meta-width meta1) (phpinspect-meta-width meta2)))
(defun phpinspect-meta-sort-start (meta1 meta2)
(< (phpinspect-meta-start meta1) (phpinspect-meta-start meta2)))
(define-inline phpinspect-meta-absolute-start (meta)
(inline-quote (caddr ,meta)))
(define-inline phpinspect-meta-overlaps-point (meta point)
"Check if META's region overlaps POINT."
(inline-letevals (point meta)
(inline-quote
(and (> (phpinspect-meta-end ,meta) ,point)
(<= (phpinspect-meta-start ,meta) ,point)))))
(defun phpinspect-meta-find-parent-matching-token (meta predicate)
"Find a parent metadata node of META, the token of which matches PREDICATE."
(if (funcall predicate (phpinspect-meta-token meta))
meta
(catch 'found
(while (phpinspect-meta-parent meta)
(setq meta (phpinspect-meta-parent meta))
(when (funcall predicate (phpinspect-meta-token meta))
(throw 'found meta))))))
(define-inline phpinspect-meta-set-parent (meta parent)
(inline-letevals (meta parent)
(inline-quote
(progn
(when ,parent
(setf (phpinspect-meta-parent-offset ,meta)
(- (phpinspect-meta-start ,meta) (phpinspect-meta-start ,parent)))
(phpinspect-meta-add-child ,parent ,meta))
(setf (phpinspect-meta-parent ,meta) ,parent)
,meta))))
;; Note: using defsubst here causes a byte code overflow
(defun phpinspect-meta-add-child (meta child)
(phpinspect-splayt-insert (phpinspect-meta-children meta) (phpinspect-meta-parent-offset child) child))
(define-inline phpinspect-meta-detach-parent (meta)
(inline-letevals (meta)
(inline-quote
(when (phpinspect-meta-parent ,meta)
;; Delete self from parent
(phpinspect-splayt-delete
(phpinspect-meta-children (phpinspect-meta-parent ,meta))
(phpinspect-meta-parent-offset ,meta))
;; Update absolute start and end
(setf (phpinspect-meta-absolute-end ,meta) (phpinspect-meta-end ,meta))
;; Note: start should always be updated after end, as end is derived from
;; it.
(setf (phpinspect-meta-absolute-start ,meta) (phpinspect-meta-start ,meta))
(setf (phpinspect-meta-parent ,meta) nil)))))
(defun phpinspect-meta-shift (meta delta)
"Move META by DELTA characters.
Negative DELTA will move to the left. Positive DELTA will move to the right.
All children are moved together (as they calculate their
positions based on the parent)."
(setf (phpinspect-meta-absolute-start meta) (+ (phpinspect-meta-start meta) delta))
(setf (phpinspect-meta-absolute-end meta) (dlet ((phpinspect-meta--point-offset-base nil))
(+ (phpinspect-meta-end meta) delta))))
(defun phpinspect-meta-right-siblings (meta)
(sort
(phpinspect-splayt-find-all-after
(phpinspect-meta-children (phpinspect-meta-parent meta)) (phpinspect-meta-parent-offset meta))
#'phpinspect-meta-sort-start))
(defun phpinspect-meta-left-sibling-tokens (meta)
(let* ((tokens (cons nil nil))
(rear tokens))
(dolist (sibling (phpinspect-meta-left-siblings meta))
(setq rear (setcdr rear (cons (phpinspect-meta-token sibling) nil))))
(cdr tokens)))
(defun phpinspect-meta-token-with-left-siblings (meta)
"Return a list containing tokens of META and all of its left siblings."
(nconc (phpinspect-meta-left-sibling-tokens meta) (list (phpinspect-meta-token meta))))
(defun phpinspect-meta-left-siblings (meta)
(sort
(phpinspect-splayt-find-all-before
(phpinspect-meta-children (phpinspect-meta-parent meta)) (phpinspect-meta-parent-offset meta))
#'phpinspect-meta-sort-start))
(define-inline phpinspect-meta--point-offset (meta point)
(inline-quote
(- ,point (or phpinspect-meta--point-offset-base (phpinspect-meta-start ,meta)))))
(cl-defmethod phpinspect-meta-find-left-sibling ((meta (head meta)))
(when (phpinspect-meta-parent meta)
(phpinspect-splayt-find-largest-before (phpinspect-meta-children (phpinspect-meta-parent meta))
(phpinspect-meta-parent-offset meta))))
(define-inline phpinspect-meta-find-right-sibling (meta)
(inline-letevals (meta)
(inline-quote
(when (phpinspect-meta-parent ,meta)
(phpinspect-splayt-find-smallest-after (phpinspect-meta-children (phpinspect-meta-parent ,meta))
(phpinspect-meta-parent-offset ,meta))))))
(define-inline phpinspect-meta-find-overlapping-child (meta point)
(inline-letevals (meta point)
(inline-quote
(if-let ((child (phpinspect-splayt-find-largest-before
(phpinspect-meta-children ,meta)
;; Use point +1 as a child starting at point still overlaps
(+ (phpinspect-meta--point-offset ,meta ,point) 1))))
(and (phpinspect-meta-overlaps-point child ,point) child)))))
(cl-defmethod phpinspect-meta-find-overlapping-children ((meta (head meta)) (point integer))
(let ((child meta)
children)
(while (and (setq child (phpinspect-meta-find-overlapping-child child point))
(phpinspect-meta-overlaps-point child point))
(push child children))
children))
(define-inline phpinspect-meta-find-child-starting-at (meta point)
(inline-letevals (meta point)
(inline-quote
(phpinspect-splayt-find (phpinspect-meta-children ,meta) (phpinspect-meta--point-offset ,meta ,point)))))
(define-inline phpinspect-meta-find-child-starting-at-recursively (meta point)
(inline-letevals (point)
(inline-quote
(catch 'phpinspect--return
(dlet ((phpinspect-meta--point-offset-base (phpinspect-meta-start ,meta)))
(let ((meta ,meta))
(while meta
(if-let ((child (phpinspect-meta-find-child-starting-at meta ,point)))
(throw 'phpinspect--return child)
(setq meta
(phpinspect-splayt-find-largest-before
(phpinspect-meta-children meta)
(phpinspect-meta--point-offset meta ,point))
phpinspect-meta--point-offset-base
(if meta (+ (phpinspect-meta-parent-offset meta) phpinspect-meta--point-offset-base)
phpinspect-meta--point-offset-base))))))))))
(defun phpinspect-meta-find-child-before (meta point)
"Find the last child of META before POINT."
(phpinspect-splayt-find-largest-before
(phpinspect-meta-children meta) (phpinspect-meta--point-offset meta point)))
(cl-defmethod phpinspect-meta-find-child-after ((meta (head meta)) (point integer))
(phpinspect-splayt-find-smallest-after
(phpinspect-meta-children meta) (phpinspect-meta--point-offset meta point)))
(define-inline phpinspect-meta-find-child-after-recursively (meta point)
(inline-letevals (point)
(inline-quote
(catch 'phpinspect--return
(dlet ((phpinspect-meta--point-offset-base (phpinspect-meta-start ,meta)))
(let ((meta ,meta))
(while meta
(if-let ((child (phpinspect-meta-find-child-after meta ,point)))
(throw 'phpinspect--return child)
(setq meta
(or (phpinspect-splayt-find-smallest-after
(phpinspect-meta-children meta)
(phpinspect-meta--point-offset meta ,point))
(phpinspect-splayt-find-largest-before
(phpinspect-meta-children meta)
(phpinspect-meta--point-offset meta ,point)))
phpinspect-meta--point-offset-base
(if meta (+ (phpinspect-meta-parent-offset meta) phpinspect-meta--point-offset-base)
phpinspect-meta--point-offset-base))))))))))
(cl-defmethod phpinspect-meta-find-child-before-recursively ((meta (head meta)) (point integer))
(let ((child meta)
last)
(while (setq child (phpinspect-meta-find-child-before child point))
(setq last child))
last))
(cl-defmethod phpinspect-meta-find-children-after ((meta (head meta)) (point integer))
(sort
(phpinspect-splayt-find-all-after
(phpinspect-meta-children meta) (phpinspect-meta--point-offset meta point))
#'phpinspect-meta-sort-start))
(cl-defmethod phpinspect-meta-find-children-before ((meta (head meta)) (point integer))
(sort (phpinspect-splayt-find-all-before
(phpinspect-meta-children meta) (phpinspect-meta--point-offset meta point))
#'phpinspect-meta-sort-start))
(defun phpinspect-meta-find-first-child-matching (meta predicate)
(cl-assert (phpinspect-meta-p meta))
(catch 'return
(phpinspect-splayt-traverse-lr (child (phpinspect-meta-children meta))
(when (funcall predicate child)
(throw 'return child)))))
(cl-defmethod phpinspect-meta-find-first-child-matching-token ((meta (head meta)) predicate)
(catch 'return
(phpinspect-splayt-traverse-lr (child (phpinspect-meta-children meta))
(when (funcall predicate (phpinspect-meta-token child))
(throw 'return child)))))
(defun phpinspect-meta-find-children-matching-token (meta predicate)
(let (result)
(phpinspect-splayt-traverse-lr (child (phpinspect-meta-children meta))
(when (funcall predicate (phpinspect-meta-token child))
(push child result)))
result))
(defun phpinspect-meta-flatten (meta)
"Flatten META and all its children into an unordered list."
(when meta
(let ((stack (list meta))
(result (list meta)))
(while-let ((current (pop stack)))
(phpinspect-splayt-traverse-lr (child (phpinspect-meta-children current))
(push child result)
(push child stack)))
result)))
(cl-defmethod phpinspect-meta-last-child ((meta (head meta)))
(phpinspect-meta-find-child-before meta (phpinspect-meta-end meta)))
(cl-defmethod phpinspect-meta-first-child ((meta (head meta)))
(phpinspect-meta-find-child-after meta (- (phpinspect-meta-start meta) 1)))
(defun phpinspect-meta-token-predicate (token-predicate)
"Wrap TOKEN-PREDICATE in a closure that operates on metadata.
The returned closure takes a metadata object as argument and then
calls TOKEN-PREDICATE on its token
slot (`phpinspect-meta-token')."
(lambda (meta) (funcall token-predicate (phpinspect-meta-token meta))))
(defun phpinspect-meta-string (meta)
(if meta
(format "[start: %d, end: %d, token: %s]"
(phpinspect-meta-start meta) (phpinspect-meta-end meta) (phpinspect-meta-token meta))
"[nil]"))
(provide 'phpinspect-meta)
;;; phpinspect-meta.el ends here