add_depends: optimise influence calculation

[git.ikiwiki.info.git] / doc / todo / dependency_types.mdwn

diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn
index d3ffdf7b2394445c0f4210667fe13741a5b6a27b..d9e68841d119bdba305da6d25f9304a2022ddf7f 100644 (file)
--- a/doc/todo/dependency_types.mdwn
+++ b/doc/todo/dependency_types.mdwn
@@ -239,6 +239,29 @@ sigh.
 >>> Hmm, I'm not seeing cycles be a problem, at least with the current
 >>> pagespec terms. --[[Joey]] 
 
 >>> Hmm, I'm not seeing cycles be a problem, at least with the current
 >>> pagespec terms. --[[Joey]] 
 

+>>>> Oh, they're not with current pagespec terms.  But this is really close to extending to handle
+>>>> functional pagespecs, etc.  And I think I'd like to think about that now.
+>>>>
+>>>> Having said that, I don't want to hold you up - you seem to be making progress.  The best is
+>>>> the enemy of the good, etc. etc.
+>>>>
+>>>> For my part, I'm imagining we have two more constructs in IkiWiki:
+>>>>
+>>>>  * A map directive that actually wikilinks to the pages it links to, and
+>>>>  * A `match_sharedLink(pageX)` matching function that matches pageY if both pageX and pageY each have links to any same third page, pageZ.
+>>>>
+>>>> With those two constructs, one page changing might change the set of pages included in a map somewhere, which might then change the set of pages matched by some other pagespec, which might then...
+>>>>
+>>>> --[[Will]]
+
+>>>>> I think that should be supported by [[bugs/transitive_dependencies]].
+>>>>> At least in the current implementation, which considers each page
+>>>>> that is rendered to be changed, and rebuilds pages that are dependent
+>>>>> on it, in a loop. An alternate implementation, which could be faster,
+>>>>> is to construct a directed graph and traverse it just once. Sounds
+>>>>> like that would probably not support what you want to do.
+>>>>> --[[Joey]]
+

 ---- 
 
 ### Link dependencies
 ---- 
 
 ### Link dependencies


@@ -255,6 +278,7 @@ sigh.
   that the page links to, which is just what link dependencies are
   triggered on.
 
   that the page links to, which is just what link dependencies are
   triggered on.
 

+[[done]]

 ----
 
 ### the removal problem
 ----
 
 ### the removal problem


@@ -279,7 +303,7 @@ One way to fix this is to include with each dependency, a list of pages
 that currently match it. If the list changes, the dependency is triggered.
 
 Should be doable, but may involve more work than
 that currently match it. If the list changes, the dependency is triggered.
 
 Should be doable, but may involve more work than

-currently. Consider that a dependency on "bugs/*" currently
+currently. Consider that a dependency on `bugs/*` currently

 is triggered by just checking until *one* page is found to match it.
 But to store the list, *every* page would have to be tried against it.
 Unless the list can somehow be intelligently updated, looking at only the
 is triggered by just checking until *one* page is found to match it.
 But to store the list, *every* page would have to be tried against it.
 Unless the list can somehow be intelligently updated, looking at only the


@@ -313,16 +337,13 @@ can indirectly influence what pages a pagespec matches.
 
 > Trying to make a formal definition of this: (Note, I'm using the term sets rather than lists, but they're roughly equivalent)
 >
 
 > Trying to make a formal definition of this: (Note, I'm using the term sets rather than lists, but they're roughly equivalent)
 >

->  * Let the *matching set* for a pagespec be the set of pages that the pagespec matches.
->  * Let a *complete influence set* for a pagespec be the set of all pages whose alteration might change the matching set of that pagespec.
->  * Let the *direct influence set* be the intersection of the matching set and the complete influence set.
->  * Let the *indirect influence set* be the compliment of the direct influence set with respect to the complete influence set.
+>  * Let the *matching set* for a pagespec be the set of existing pages that the pagespec matches.
+>  * Let a *influence set* for a pagespec be the set of all pages, *p*, whose alteration might:
+>    * cause the pagespec to include or exclude a page other than *p*, or
+>    * cause the pagespec to exclude *p*.
+>
+>> \[Will snipped some stuff and edited the formal definition]

 >
 >

-> Is that a fair definition?  I don't think it quite matches your examples below unfortunately.
-> I was unsure if I should insert the word 'existing' in there in a few places.  As it stands, these definitions could include sets of pages that don't exist, e.g. "*".
-> The one I'm least sure of is the definition of the direct influence set.  It feels like you want something
-> like "the traditional set of things we thought about that could cause a pagespec to change", but that definition
-> is not very formal and I suspect will lead to problems.  Something like "The set of pages matched by the globs in the pagespec" might be closer?

 > --[[Will]]
 
 >> I appreciate the formalism! 
 > --[[Will]]
 
 >> I appreciate the formalism! 


@@ -331,15 +352,36 @@ can indirectly influence what pages a pagespec matches.
 >> in the future, the existing dependency code will always test to see
 >> if it matches. So it will be in the maching set (or not) at that point.
 >>
 >> in the future, the existing dependency code will always test to see
 >> if it matches. So it will be in the maching set (or not) at that point.
 >>

+>>> Hrm, I agree with you in general, but I think I can come up with nasty counter-examples.  What about a pagespec
+>>> of "!backlink(bogus)" where the page bogus doesn't exist?  In this case, the page 'bogus' needs to be in the influence
+>>> set even though it doesn't exist.
+>>>
+>>>> I think you're right, this is a case that the current code is not
+>>>> handling. Actually, I made all the pagespecs return influences
+>>>> even if the influence was not present or did not match. But, it
+>>>> currently only records influences as dependencies when a pagespec
+>>>> successfully matches. Now I'm sure that is wrong, and I've removed
+>>>> that false optimisation. I've updated some of the below. --[[Joey]]
+>>>
+>>> Also, I would really like the formalism to include the whole dependency system, not just any additions to it.  That will make
+>>> the whole thing much easier to reason about.
+>>

 >> The problem with your definition of direct influence set seems to be
 >> that it doesn't allow `link()` and `title()` to have as an indirect
 >> influence, the page that matches. But I'm quite sure we need those.
 >>  --[[Joey]] 
 
 >> The problem with your definition of direct influence set seems to be
 >> that it doesn't allow `link()` and `title()` to have as an indirect
 >> influence, the page that matches. But I'm quite sure we need those.
 >>  --[[Joey]] 
 

+>>> I see what you mean.  Does the revised definition capture this effectively?
+>>> The problem with this revised definition is that it still doesn't match your examples below.
+>>> My revised definition will include pretty much all currently matching pages to be in the influence list
+>>> because deletion of any of them would cause a change in which pages are matched - the removal problem.
+>>> -- [[Will]]
+

 #### Examples
 
 * The pagespec "created_before(foo)" has an influence list that contains foo.
 #### Examples
 
 * The pagespec "created_before(foo)" has an influence list that contains foo.

-  The removal or (re)creation of foo changes what pages match it.
+  The removal or (re)creation of foo changes what pages match it. Note that
+  this is true even if the pagespec currently fails to match.

 
 * The pagespec "foo" has an empty influence list. This is because a
   modification/creation/removal of foo directly changes what the pagespec
 
 * The pagespec "foo" has an empty influence list. This is because a
   modification/creation/removal of foo directly changes what the pagespec


@@ -349,13 +391,30 @@ can indirectly influence what pages a pagespec matches.
   Avoiding including every page in the wiki into its influence list is
   very important!
 
   Avoiding including every page in the wiki into its influence list is
   very important!
 

+>>> So, why don't the above influence lists contain the currently matched pages?
+>>> Don't you need this to handle the removal problem? -- [[Will]]
+
+>>>> The removal problem is slightly confusingly named, since it does not
+>>>> affect pages that were matched by a glob and have been removed. Such
+>>>> pages can be handled without being influences, because ikiwiki knows
+>>>> they have been removed, and so can still match them against the
+>>>> pagespec, and see they used to match; and thus knows that the
+>>>> dependency has triggered.
+>>>>
+>>>> Maybe the thing to do is consider this an optimisation, where such
+>>>> pages are influences, but ikiwiki is able to implicitly find them,
+>>>> so they do not need to be explicitly stored. --[[Joey]]
+

 * The pagespec "title(foo)" has an influence list that contains every page
   that currently matches it. A change to any matching page can change its
   title, making it not match any more, and so the list is needed due to the
 * The pagespec "title(foo)" has an influence list that contains every page
   that currently matches it. A change to any matching page can change its
   title, making it not match any more, and so the list is needed due to the

-  removal problem.
+  removal problem. A page that does not have a matching title is not an
+  influence, because modifying the page to change its title directly
+  changes what the pagespec matches.

 
 * The pagespec "backlink(index)" has an influence list
   that contains index (because a change to index changes the backlinks).
 
 * The pagespec "backlink(index)" has an influence list
   that contains index (because a change to index changes the backlinks).

+  Note that this is true even if the backlink currently fails.

 
 * The pagespec "link(done)" has an influence list that
   contains every page that it matches. A change to any matching page can
 
 * The pagespec "link(done)" has an influence list that
   contains every page that it matches. A change to any matching page can


@@ -417,7 +476,63 @@ Given that, the `backlink` will always be evalulated, and will put index
 onto the influence list. If we combine the influences from each
 successful match, we get the right result.
 
 onto the influence list. If we combine the influences from each
 successful match, we get the right result.
 

-> This is implemented, seems to work ok. --[[Joey]] 
+> This is implemented, seems to work ok. --[[Joey]]
+
+> `or` short-circuits too, but the implementation correctly uses `|`,
+> which I assume is what you meant. --[[smcv]]
+
+>> Er, yeah. --[[Joey]] 
+
+----
+
+What about: "!link(done)"
+
+Specifically, I want to make sure it works now that I've changed
+`match_link` to only return a page as an influence if it *does*
+link to done.
+
+So, when matching against page P, that does not link to done,
+there are no influences, and the pagespec matches. If P is later
+changed to add a link to done, then the dependency resolver will directly
+notice that.
+
+When matching against page P, that does link to done, P
+is an influence, and the pagespec does not match. If P is later changed
+to not link to done, the influence will do its job.
+
+Looks good!
+
+----
+
+Here is a case where this approach has some false positives.
+
+"bugs/* and link(patch)"
+
+This finds as influences all pages that link to patch, even
+if they are not under bugs/, and so can never match.
+
+To fix this, the influence calculation would need to consider boolean
+operators. Currently, this turns into roughly:
+
+`FailReason() & SuccessReason(patch)`
+
+Let's say that the glob instead returns a HardFailReason, which when
+ANDed with another object, drops their influences. (But when ORed, combines
+them.) Fixes the above, but does it always work?
+
+"(bugs/* or link(patch)) and backlink(index)" =>
+`( HardFailReason() | SuccessReason(page) ) & SuccessReason(index)`` =>
+`SuccessReason(page & SuccessReason(index)` =>
+SuccessReason(page, index) => right
+
+"(bugs/* and link(patch)) or backlink(index)" =>
+`( HardFailReason() & SuccessReason(page) ) | SuccessReason(index)`` =>
+`HardFailReason() | SuccessReason(index)` =>
+`SuccessReason(index)` => right
+
+"!bugs/* and link(patch)" =>
+`HardFailReason() | SuccessReason(bugs/foo)` =>  
+`HardFailReason()` => right

 
 #### High-level Calculation and Storage
 
 
 #### High-level Calculation and Storage