]> sipb.mit.edu Git - ikiwiki.git/blob - doc/todo/dependency_types.mdwn
Merge branch 'master' into dependency-types
[ikiwiki.git] / doc / todo / dependency_types.mdwn
1 Ikiwiki currently only has one type of dependency between pages
2 (plus wikilinks special cased in on the side). This has resulted in various
3 problems, and it's seemed for a long time to me that ikiwiki needs to get
4 smarter about what types of dependencies are supported.
5
6 ### unnecessary work
7
8 The current single dependency type causes the depending page to be rebuilt
9 whenever a matching dependency is added, removed, or *modified*. But a
10 great many things don't care about the modification case, and often cause
11 unnecessary page rebuilds:
12
13 * map only cares if the pages are added or removed. Content change does
14   not matter (unless show=title is used).
15 * brokenlinks, orphans, pagecount, ditto (generally)
16 * inline in archive mode cares about page title, author changing, but
17   not content. (Ditto for meta with show=title.)
18 * Causes extra work when solving the [[bugs/transitive_dependencies]]
19   problem.
20
21 ### two types of dependencies needed for [[tracking_bugs_with_dependencies]]
22
23 >>  it seems that there are two types of dependency, and ikiwiki
24 >>  currently only handles one of them.  The first type is "Rebuild this
25 >>  page when any of these other pages changes" - ikiwiki handles this.
26 >>  The second type is "rebuild this page when set of pages referred to by
27 >>  this pagespec changes" - ikiwiki doesn't seem to handle this.  I
28 >>  suspect that named pagespecs would make that second type of dependency
29 >>  more important.  I'll try to come up with a good example. -- [[Will]]
30
31 >>> Hrm, I was going to build an example of this with backlinks, but it
32 >>> looks like that is handled as a special case at the moment (line 458 of
33 >>> render.pm).  I'll see if I can breapk
34 >>> things another way.  Fixing this properly would allow removal of that special case. -- [[Will]]
35
36 >>>> I can't quite understand the distinction you're trying to draw
37 >>>> between the two types of dependencies. Backlinks are a very special
38 >>>> case though and I'll be suprised if they fit well into pagespecs.
39 >>>> --[[Joey]] 
40
41 >>>>> The issue is that the existential pagespec matching allows you to build things that have similar
42 >>>>> problems to backlinks.
43 >>>>> e.g. the following inline:
44
45     \[[!inline pages="define(~done, link(done)) and link(~done)" archive=yes]]
46
47 >>>>> includes any page that links to a page that links to done.  Now imagine I add a new link to 'done' on
48 >>>>> some random page somewhere - a page which some other page links to which didn't previously get included - the set of pages accepted by the pagespec, and hence the set of
49 >>>>> pages inlined, will change.  But, there is no dependency anywhere on the page that I altered, so
50 >>>>> ikiwiki will not rebuild the page with the inline in it.  What is happening is that the page that I altered affects
51 >>>>> the set of pages matched by the pagespec without itself being matched by the pagespec, and hence included in the dependency list.
52
53 >>>>> To make this work well, I think you need to recognise two types of dependencies for each page (and no
54 >>>>> special cases for particular types of links, eg backlinks).  The first type of dependency says, "The content of
55 >>>>> this page depends upon the content of these other pages".  The `add_depends()` in the shortcuts
56 >>>>> plugin is of this form: any time the shortcuts page is edited, any page with a shortcut on it
57 >>>>> is rebuilt.  The inline plugin also needs to add dependencies of this form to detect when the inlined
58 >>>>> content changes.  By contrast, the map plugin does not need a dependency of this form, because it
59 >>>>> doesn't actually care about the content of any pages, just which pages it needs to include (which we'll handle next).
60
61 >>>>> The second type of dependency says, "The content of this page depends upon the exact set of pages matched
62 >>>>> by this pagespec".  The first type of dependency was about the content of some pages, the second type is about
63 >>>>> which pages get matched by a pagespec.  This is the type of dependency tracking that the map plugin needs.
64 >>>>> If the set of pages matched by map pagespec changes, then the page with the map on it needs to be rebuilt to show a different list of pages.
65 >>>>> Inline needs this type of dependency as well as the previous type - This type handles a change in which pages
66 >>>>> are inlined, the previous type handles a change in the content of any of those pages.  Shortcut does not need this type of
67 >>>>> dependency.  Most of the places that use `add_depends()` seem to need this type of dependency rather than the first type.
68
69 >>>>>> Note that inline and map currently achieve the second type of dependency by
70 >>>>>> explicitly calling `add_depends` for each page the displayed.
71 >>>>>> If any of those pages are removed, the regular pagespec would not
72 >>>>>> match them -- since they're gone. However, the explicit dependency
73 >>>>>> on them does cause them to match. It's an ugly corner I'd like to
74 >>>>>> get rid of. --[[Joey]]
75
76 >>>>> Implementation Details:  The first type of dependency can be handled very similarly to the current
77 >>>>> dependency system.  You just need to keep a list of pages that the content depends upon.  You could
78 >>>>> keep that list as a pagespec, but if you do this you might want to check that the pagespec doesn't change,
79 >>>>> possibly by adding a dependency of the second type along with the dependency of the first type.
80
81 >>>>>> An example of the current system not tracking enough data is 
82 >>>>>> described in [[bugs/transitive_dependencies]].
83 >>>>>> --[[Joey]] 
84
85 >>>>> The second type of dependency is a little more tricky.  For each page, we'd need a list of pagespecs that
86 >>>>> the page depended on, and for each pagespec you'd want to store the list of pages that currently match it.
87 >>>>> On refresh, you'd need to check each pagespec to see if the set of pages that match it has changed, and if
88 >>>>> that set has changed, then rebuild the dependent page(s).  Oh, and for this second type of dependency, I
89 >>>>> don't think you can merge pagespecs.  If I wanted to know if either "\*" or "link(done)" changes, then just checking
90 >>>>> to see if the set of pages matched by "\* or link(done)" changes doesn't work.
91
92 >>>>> The current system works because even though you usually want dependencies of the second type, the set of pages
93 >>>>> referred to by a pagespec can only change if one of those pages itself changes.  i.e. A dependency check of the
94 >>>>> first type will catch a dependency change of the second type with current pagespecs.
95 >>>>> This doesn't work with backlinks, and it doesn't work with existential matching.  Backlinks are currently special-cased.  I don't know
96 >>>>> how to special-case existential matching - I suspect you're better off just getting the dependency tracking right.
97
98 >>>>> I also tried to come up with other possible solutions: e.g. can we find the dependencies for a pagespec?  That
99 >>>>> would be the set of pages where a change on one of those pages could lead to a change in the set of pages matched by the pagespec.
100 >>>>> For old-style pagespecs without backlinks, the dependency set for a pagespec is the same as the set of pages the pagespec matches.
101 >>>>> Unfortunately, with existential matching, the set of pages that each
102 >>>>> pagespec depends upon can quickly become "*", which is not very useful.  -- [[Will]]
103
104 ### proposal
105
106 I propose the following. --[[Joey]] 
107
108 * Add a second type of dependency, call it an "presence dependency".
109 * `add_depends` defaults to adding a regular ("full") dependency, as
110   before. (So nothing breaks.)
111 * `add_depends($page, $spec, presence => 0)` adds an presence dependency.
112 * `refresh` only looks at added/removed pages when resolving presence
113   dependencies.
114
115 This seems straightforwardly doable. I'd like [[Will]]'s feedback on it, if
116 possible. The type types of dependencies I am proposing are not identical
117 to the two types he talks about above, but I hope are close enough that
118 they can be used.
119
120 This doesn't deal with the stuff that only depend on the metadata of a
121 page, as collected in the scan pass, changing.  But it does leave a window
122 open for adding such a dependency type later.
123
124 ----
125
126 I implemented the above in a branch.
127 [[!template id=gitbranch branch=origin/dependency-types author="[[joey]]"]]
128
129 Then I found some problems:
130
131 * Something simple like pagecount, that seems like it could use a
132   presence dependency, can have a pagespec that uses metadata, like
133   `author()` or `copyright()`.
134 * pagestats, orphans and brokenlinks cannot use presence dependencies
135   because they need to update when links change.
136
137 Now I'm thinking about having a special dependency look at page
138 metadata, and fire if the metadata changes. And it seems links should
139 either be included in that, or there should be a way to make a dependency
140 that fires when a page's links change. (And what about backlinks?)
141
142 It's easy to see when a page's links change, since there is `%oldlinks`.
143 To see when metadata is changed is harder, since it's stored in the
144 pagestate by the meta plugin. Also, there are many different types of
145 metadata, that would need to be matched with the pagespecs somehow.
146
147 Quick alternative: Make add_depends look at the pagespec. Ie, if it
148 is a simple page name, or a glob, we know a presence dependency
149 can be valid. If's more complex, convert the dependency from
150 presence to full.
151
152 There is a lot to dislike about this method. Its parsing of the pagespec,
153 as currently implemented, does not let plugins add new types of pagespecs
154 that only care about presence. Its pagespec parsing is also subject to
155 false negatives (though these should be somewhat rare, and no false
156 positives). Still, it does work, and it makes things like simple maps and
157 pagecounts much more efficient.
158
159 ----
160
161 #### Will's first pass feedback.
162
163 If the API is going to be updated, then it would be good to make it forward compatible.
164 I'd like for the API to be extendible to what is useful for complex pagespecs, even if we
165 that is a little redundant at the moment.
166
167 My attempt to play with this is in my git repo.  [[!template id=gitbranch branch=origin/depends-spec author="[[will]]"]]
168 That branch is a little out of date, but if you just look at the changes in IkiWiki.pm you'll see the concept I was looking at.
169 I added an "add_depends_spec()" function that adds a dependency on the pagespec passed to it.  If the set of matched pages
170 changes, then the dependent page is rebuilt.  At the moment the implementation uses the same hack used by map and inline -
171 just add all the pages that currently exist as traditional content dependencies.
172
173 Getting back to commenting on your proposal:
174
175 Just talking about the definition of a "presence dependency" for the moment, and ignoring implementation.  Is a
176 "presence dependency" supposed to cause an update when a page disappears?  I assume so.  Is a presence dependency
177 supposed to cause an update when a pages existence hasn't changed, but it no longer matches the pagespec.
178 (e.g. you use `created_before(test_page)` in a pagespec, and there was a page, `new_page`, that was created
179 after `test_page`.  `new_page` will not match the spec.  Now we'll delete and then re-create `test_page`.  Now
180 `new_page` will match the spec, and yet `new_page` itself hasn't changed.  Nor has its 'presence' - it was present
181 before and it is present now.  Should this cause a re-build of any page that has a 'presence' dependency on the spec?
182
183 I think that is another version of the problem you encountered with meta-data.
184
185 In the longer term I was thinking we'd have to introduce a concept of 'internal pagespec dependencies'.  Note that I'm
186 defining 'internal' pagespec dependencies differently to the pagespec dependencies I defined above.  Perhaps an example:
187 If you had a pagespec that was `created_before(test_page)`, then you could list all pages created before `test_page`
188 with a `map` directive.  The map directive would add a pagespec dependency on `created_before(test_page)`.
189 Internally, there would be a second page-spec parsing function that discovers which pages a given pagespec
190 depends on.  As well as the function `match_created_before()`, we'd have to add a new function `depend_created_before()`.
191 This new function would return a list of pages, which when any of them change, the output of `match_created_before()`
192 would change.  In this example, it would just return `test_page`.
193
194 These lists of dependent pages could just be concatenated for every `match_...()` function in a pagespec - you can ignore
195 the boolean formula aspects of the pagespec for this.  If a content dependency were added on these pages, then I think 
196 the correct rebuilds would occur.  
197
198 In all, this is a surprisingly difficult problem to solve perfectly.  Consider the following case:
199
200 PageA.mdwn:
201
202 > [ShavesSelf]
203
204 PageB.mdwn
205
206 > Doesn't shave self.
207
208 ShavedByBob.mdwn:
209
210 > [!include pages="!link(ShavesSelf)"]
211
212 Does ShavedByBob.mdwn include itself?
213
214 (Yeah - in IkiWiki currently links are included by include, but the idea holds.  I had a good example a while back, but I can't think of it right now.)
215
216 sigh.
217
218 -- [[Will]]
219
220 ---- 
221
222 ### Link dependencies
223
224 * `add_depends($page, $spec, links => 1, presence => 1)`
225   adds a links + presence dependency.
226 * Use backlinks change code to detect changes to link dependencies too.
227 * So, brokenlinks can fire whenever any links in any of the
228   pages it's tracking change, or when pages are added or
229   removed.
230 * To determine if a pagespec is valid to be used with a links dependency,
231   use the same set that are valid for presence dependencies. But also
232   allow `backlinks()` to be used in it, since that matches pages
233   that the page links to, which is just what link dependencies are
234   triggered on.
235
236 [[done]]
237 ----
238
239 ### the removal problem
240
241 So far I have not addressed fixing the removal problem (which Will
242 discusses above).
243
244 Summary of problem: A has a dependency on a pagespec such as
245 "bugs/* and !link(done)". B currently matches. Then B is updated,
246 in a way that makes A's dependency not match it (ie, it links to done).
247 Now A is not updated, because ikiwiki does not realize that it
248 depended on B before.
249
250 This was worked around to fix [[bugs/inline_page_not_updated_on_removal]]
251 by inline and map adding explicit dependencies on each page that appears
252 on them. Then a change to B triggers the explicit dep. While this works,
253 it's 1) ugly 2) probably not implemented by all plugins that could
254 be affected by this problem (ie, linkmap) and 3) is most of the reason why
255 we grew the complication of `depends_simple`.
256
257 One way to fix this is to include with each dependency, a list of pages
258 that currently match it. If the list changes, the dependency is triggered.
259
260 Should be doable, but seems to involve a more work than
261 currently. Consider that a dependency on "bugs/*" currently
262 is triggered by just checking until *one* page is found to match it.
263 But to store the list, *every* page would have to be tried against it.
264 Unless the list can somehow be intelligently updated, looking at only the
265 changed pages.