Does ShavedByBob.mdwn include itself?
-(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.)
+(Yeah - in IkiWiki currently links are *not* included by include, but the idea holds. I had a good example a while back, but I can't think of it right now.)
sigh.
> to determine what metadata, pages, etc they depend on. It is indeed
> tricky to do. More thoughts on influence lists a bit below. --[[Joey]]
+>> The big part of what makes this tricky is that there may be cycles in the
+>> dependency graph. This can lead to situations where the result is just not
+>> well defined. This is what I was trying to get at above. -- [[Will]]
+
+>>> 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]]
+
+>>>>>> Yes - that's what I'm talking about - I'll add some comments there. -- [[Will]]
+
----
### Link dependencies
* `add_depends($page, $spec, links => 1, presence => 1)`
adds a links + presence dependency.
-* `refresh` only rebuilds a page with a links dependency if
- pages matched by the pagespec gain or lose links. (What the link
- actually points to may change independent of this, due to changes
- elsewhere, without it firing.)
+* Use backlinks change code to detect changes to link dependencies too.
* So, brokenlinks can fire whenever any links in any of the
pages it's tracking change, or when pages are added or
removed.
that the page links to, which is just what link dependencies are
triggered on.
+[[done]]
----
### the removal problem
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
I'm using this term for the concept of a list of pages whose modification
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)
+>
+> * Let the *matching set* for a pagespec be the set of existing pages that the pagespec matches.
+> * Let the *missing document matching set* be the set of pages that would match the spec if they didn't exist. These pages may or may not currently exist. Note that membership of this set depends upon how the `match_()` functions react to non-existant pages.
+> * Let the *indirect 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*, unless the alteration is the removal of *p* and *p* is in the missing document matching set.
+>
+> Justification: The 'base dependency mechanism' is to compare changed pages against each pagespec. If the page matches, then rebuild the spec. For this comparison, creation and removal
+> of pages are both considered changes. This base mechanism will catch:
+>
+> * The addition of any page to the matching set through its own modification/creation
+> * The removal of any page *that would still match while non-existant* from the matching set through its own removal. (Note: The base mechanism cannot remove a page from the matching set because of that page's own modification (not deletion). If the page should be removed matching set, then it obviously cannot match the spec after the change.)
+> * The modification (not deletion) of any page that still matches after the modification.
+>
+> The base mechanism may therefore not catch:
+>
+> * The addition or removal of any page from the matching set through the modification/addition/removal of any other page.
+> * The removal of any page from the matching set through its own modification/removal if it does not still match after the change.
+>
+> The indirect influence set then should handle anything that the base mechanism will not catch.
+>
+> --[[Will]]
+
+>> I appreciate the formalism!
+>>
+>> Only existing pages need to be in these sets, because if a page is added
+>> 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]]
+
+>>> 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.
- The removal or (re)creation of foo changes what pages match it.
+* The pagespec "created_before(foo)" has an indirect influence list that contains foo.
+ 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.
+
+>>> This is an annoying example (hence well worth having :) ). I think the
+>>> indirect influence list must contain 'foo' and all currently matching
+>>> pages. `created_before(foo)` will not match
+>>> a deleted page, and so the base mechanism would not cause a rebuild. The
+>>> removal problem strikes. -- [[Will]]
+
+>>>> But `created_before` can in fact match a deleted page. Because the mtime
+>>>> of a deleted page is temporarily set to 0 while the base mechanism runs to
+>>>> find changes in deleted pages. (I verified this works by experiment,
+>>>> also that `created_after` is triggered by a deleted page.) --[[Joey]]
+
+>>>>> Oh, okie. I looked at the source, saw the `if (exists $IkiWiki::pagectime{$testpage})` and assumed it would fail.
+>>>>> Of course, having it succeed doesn't cure all the issues -- just moves them. With `created_before()` succeeding
+>>>>> for deleted files, this pagespec will be match any removal in the entire wiki with the base mechanism. Whether this is
+>>>>> better or worse than the longer indirect influence list is an empirical question. -- [[Will]]
* The pagespec "foo" has an empty influence list. This is because a
modification/creation/removal of foo directly changes what the pagespec
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.
+>>>>
+>>>>> IkiWiki can only see that they used to match if they're in the glob matching set. -- [[Will]]
+>>>>
+>>>> 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. Why is that considered an indirect influence? Well, the pagespec
- might be used in a presence dependency, and so its title changing
- would not directly affect the dependency.
+ title, making it not match any more, and so the list is needed due to the
+ 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).
+ Note that this is true even if the backlink currently fails.
+
+>>> This is another interesting example. The missing document matching set contains all links on the page index, and so
+>>> the influence list only needs to contain 'index' itself. -- [[Will]]
* The pagespec "link(done)" has an influence list that
contains every page that it matches. A change to any matching page can
remove a link and make it not match any more, and so the list is needed
due to the removal problem.
+>> Why doesn't this include every page? If I change a page that doesn't have a link to
+>> 'done' to include a link to 'done', then it will now match... or is that considered a
+>> 'direct match'? -- [[Will]]
+
+>>> The regular dependency calculation code will check if every changed
+>>> page matches every dependency. So it will notice the link was added.
+>>> --[[Joey]]
+
#### Low-level Calculation
One way to calculate a pagespec's influence would be to
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:
-#### High-level Calculation and Storage
+`FailReason() & SuccessReason(patch)`
-Calculating the full influence list for a pagespec requires trying to match
-it against every page in the wiki.
+Let's say that the glob instead returns a HardFailReason, which when
+ANDed with another object, blocks their influences. (But when ORed,
+combines them.)
-I'd like to avoid doing such expensive matching redundantly. So add a
-`pagespec_match_all`, which returns a list of all pages in the whole
-wiki that match the pagespec, and also adds the pagespec as a dependency,
-and while it's at it, calculates and stores the influence list.
+Question: Are all pagespec terms that return reason objects w/o any
+influence info, suitable to block influence in this way?
-It could have an optional sort parameter, and limit parameter, to control
-how many items to return and the sort order. So when inline wants to
-display the 10 newest, only the influence lists for those ten are added.
+To be suitable to block, a term should never change from failing to match a
+page to successfully matching it, unless that page is directly changed in a
+way that influences are not needed for ikiwiki to notice. But, if a term
+did not meet these criteria, it would have an influence. QED.
-If `pagespec_match_depends` can be used by all plugins, then great,
-influences are automatically calculated, no extra work needs to be done.
+#### Influence types
-If not, and some plugins still need to use `pagespec_match_list` or
-`pagespec_match`, and `add_depends`, then I guess that `add_depends` can do
-a slightly more expensive influence calculation.
+Note that influences can also have types, same as dependency types.
+For example, "backlink(foo)" has an influence of foo, of type links.
+"created_before(foo)" also is influenced by foo, but it's a presence
+type. Etc.
-Bonus: If `add_depends` is doing an influence calculation, then I can remove
-the nasty hack it currently uses to decide if a given pagespec is safe to use
-with an existence or links dependency.
+> This is an interesting concept that I hadn't considered. It might
+> allow significant computational savings, but I suspect will be tricky
+> to implement. -- [[Will]]
-Where to store the influence list? Well, it appears that we can just add
-(content) dependencies for each item on the list, to the page's
-regular list of simple dependencies. So, the data stored ends up looking
-just like what is stored today by the explicit dependency hacks. Except,
-it's calculated more smartly, and is added automatically.
+>> It was actually really easy to implement it, assuming I picked the right
+>> dependency types of course. --[[Joey]]