From a198c89e8f968549416d3871bddafa831240e6b8 Mon Sep 17 00:00:00 2001 From: "http://www.cse.unsw.edu.au/~willu/" Date: Thu, 8 Oct 2009 21:09:08 -0400 Subject: Minor comment --- doc/todo/dependency_types.mdwn | 2 ++ 1 file changed, 2 insertions(+) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index f06603874..d2b121d81 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -262,6 +262,8 @@ sigh. >>>>> 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 -- cgit v1.2.3 From d73c54b9a7406f4f8d23b2a36e1968bba70f1089 Mon Sep 17 00:00:00 2001 From: "http://www.cse.unsw.edu.au/~willu/" Date: Thu, 8 Oct 2009 21:30:17 -0400 Subject: comments on cycles in the dependency graph --- doc/bugs/transitive_dependencies.mdwn | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'doc') diff --git a/doc/bugs/transitive_dependencies.mdwn b/doc/bugs/transitive_dependencies.mdwn index 9586bc9b0..bdad67f60 100644 --- a/doc/bugs/transitive_dependencies.mdwn +++ b/doc/bugs/transitive_dependencies.mdwn @@ -66,3 +66,20 @@ Downsides here: plugins, and could be solved by adding more dependency types.) --[[Joey]] + +> Some questions/comments... I've thought about this a lot for [[todo/tracking_bugs_with_dependencies]]. +> +> * When you say that anything that causes a rebuild of B is treated as a change of B, are you: i) Treating +> any rebuild as a change, or ii) Treating any rebuild that gives a new result as a change? Option ii) would +> lead to fewer rebuilds. Implementation is easy: when you're about to rebuild a page, load the old rendered html in. Do the rebuild. Compare +> the new and old html. If there is a difference, then mark that page as having changed. If there is no difference +> then you don't need to mark that pages as changed, even though it has been rebuilt. (This would ignore pages in meta-data that don't +> cause changes in html, but I don't think that is a huge issue.) +> * The second comment I have relates to cycles in transitive dependencies. At the moment I don't think this is +> possible, but with some additions it may well become so. This could be problematic as it could lead to a) +> updates that never complete, or b) it being theoretically unclear what the final result should be (i.e. you +> can construct logical paradoxes in the system). I think the point above about marking things as changed only when +> the output actually changes fixes any cases that are well defined. For logical paradoxes and infinite loops (e.g. +> two pages that include each other), you might want to put a limit on the number of times you'll rebuild a page in any +> given run of ikiwiki. Say, only allow a page to rebuild twice on any run, regardless of whether a page it depends on changes. +> This is not a perfect solution, but would be a good approximation. -- [[Will]] -- cgit v1.2.3 From 0e2ce171c9e897b6b55d31cfeff7566f7adab7b8 Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Thu, 8 Oct 2009 22:31:13 -0400 Subject: response --- doc/bugs/transitive_dependencies.mdwn | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'doc') diff --git a/doc/bugs/transitive_dependencies.mdwn b/doc/bugs/transitive_dependencies.mdwn index bdad67f60..70b5fb4d4 100644 --- a/doc/bugs/transitive_dependencies.mdwn +++ b/doc/bugs/transitive_dependencies.mdwn @@ -75,6 +75,13 @@ Downsides here: > the new and old html. If there is a difference, then mark that page as having changed. If there is no difference > then you don't need to mark that pages as changed, even though it has been rebuilt. (This would ignore pages in meta-data that don't > cause changes in html, but I don't think that is a huge issue.) + +>> That is a good idea. I will have to look at it to see if the overhead of +>> reading back in the html of every page before building actually is a +>> win though. So far, I've focused on avoiding unnecessary rebuilds, and +>> there is still some room for more dependency types doing so. +>> (Particularly for metadata dependencies..) --[[Joey]] + > * The second comment I have relates to cycles in transitive dependencies. At the moment I don't think this is > possible, but with some additions it may well become so. This could be problematic as it could lead to a) > updates that never complete, or b) it being theoretically unclear what the final result should be (i.e. you @@ -83,3 +90,5 @@ Downsides here: > two pages that include each other), you might want to put a limit on the number of times you'll rebuild a page in any > given run of ikiwiki. Say, only allow a page to rebuild twice on any run, regardless of whether a page it depends on changes. > This is not a perfect solution, but would be a good approximation. -- [[Will]] + +>> Ikiwiki only builds any given output file once per run, already. --[[Joey]] -- cgit v1.2.3 From 4299f22ae8b20f3cbc23876c8fac0a0856a164c2 Mon Sep 17 00:00:00 2001 From: "http://www.cse.unsw.edu.au/~willu/" Date: Thu, 8 Oct 2009 22:36:29 -0400 Subject: Another tweak to the formal definition. --- doc/todo/dependency_types.mdwn | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index d2b121d81..465796135 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -339,11 +339,25 @@ 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 a *influence set* for a pagespec be the set of all pages, *p*, whose alteration might: +> * Let the *assignment dependent glob matching set* for a particular assignment of True/False to the `match_()` functions of a pagespec, be the set of pages that would match if the `match_()` functions returned those true/false values. +> * Let the *glob matching set* be the intersection of all assignment dependent glob matching sets. i.e. the set of pages that can match this pagespec just based on glob information, regardless of what the `match_()` functions return. +> * 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*. +> * cause the pagespec to exclude *p* unless *p* is in the glob matching set. > ->> \[Will snipped some stuff and edited the formal definition] +> 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 if it existed* from the matching set through its own removal. (Note: The base mechanism cannot remove a page cannot from the matching set because of that page's own modification. If the page should be removed, then cannot match the spec after the change.) This 'match after the change' criterion is what I tried to capture in the glob matching set above. I think my glob matching set is slightly more restrictive than the set of pages that 'still match after the change', but more restrictive is safer than less restrictive for that set. +> +> 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. +>> At the moment the indirect influence set is a little conservative, in that the glob matching set doesn't exactly equal the set of pages that still match after the change. It is quite hard to get this right - thoughts on tuning the glob matching set definition are welcome. I've tried to err on the side of a longer indirect influence set, as that will make sure we do enough updates. > > --[[Will]] @@ -380,10 +394,13 @@ can indirectly influence what pages a pagespec matches. #### Examples -* The pagespec "created_before(foo)" has an influence list that contains foo. +* 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. 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. Note that the glob matching set is empty in this case. -- [[Will]] + * The pagespec "foo" has an empty influence list. This is because a modification/creation/removal of foo directly changes what the pagespec matches. @@ -402,6 +419,8 @@ can indirectly influence what pages a pagespec matches. >>>> 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]] -- cgit v1.2.3 From 6533bec35af422d2db3b5b7347e883035fea6e99 Mon Sep 17 00:00:00 2001 From: "http://www.cse.unsw.edu.au/~willu/" Date: Thu, 8 Oct 2009 22:59:34 -0400 Subject: Yet another tweak to the formal definition. Much better this time. --- doc/todo/dependency_types.mdwn | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index 465796135..9a031aac9 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -339,17 +339,17 @@ 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 *assignment dependent glob matching set* for a particular assignment of True/False to the `match_()` functions of a pagespec, be the set of pages that would match if the `match_()` functions returned those true/false values. -> * Let the *glob matching set* be the intersection of all assignment dependent glob matching sets. i.e. the set of pages that can match this pagespec just based on glob information, regardless of what the `match_()` functions return. +> * 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 *p* is in the glob matching set. +> * 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 if it existed* from the matching set through its own removal. (Note: The base mechanism cannot remove a page cannot from the matching set because of that page's own modification. If the page should be removed, then cannot match the spec after the change.) This 'match after the change' criterion is what I tried to capture in the glob matching set above. I think my glob matching set is slightly more restrictive than the set of pages that 'still match after the change', but more restrictive is safer than less restrictive for that set. +> * 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 cannot 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: > @@ -357,7 +357,6 @@ can indirectly influence what pages a pagespec matches. > * 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. ->> At the moment the indirect influence set is a little conservative, in that the glob matching set doesn't exactly equal the set of pages that still match after the change. It is quite hard to get this right - thoughts on tuning the glob matching set definition are welcome. I've tried to err on the side of a longer indirect influence set, as that will make sure we do enough updates. > > --[[Will]] @@ -398,8 +397,8 @@ can indirectly influence what pages a pagespec matches. 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. 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. Note that the glob matching set is empty in this case. -- [[Will]] +>>> 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]] * The pagespec "foo" has an empty influence list. This is because a modification/creation/removal of foo directly changes what the pagespec @@ -436,6 +435,9 @@ can indirectly influence what pages a pagespec matches. 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 -- cgit v1.2.3 From f977eaf39493984924b6ae9409be3e1d504fc0ae Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Fri, 9 Oct 2009 14:52:03 -0400 Subject: response --- doc/todo/dependency_types.mdwn | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index 9a031aac9..6ca06fdab 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -348,7 +348,7 @@ can indirectly influence what pages a pagespec matches. > 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 cannot 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 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: @@ -397,8 +397,16 @@ can indirectly influence what pages a pagespec matches. 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]] +>>> 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]] * The pagespec "foo" has an empty influence list. This is because a modification/creation/removal of foo directly changes what the pagespec -- cgit v1.2.3 From 2ba8bd386142e7f3c0fb03c86eb90eb3885aabd2 Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Fri, 9 Oct 2009 17:19:07 -0400 Subject: remove highlevel influence calculation stuff I have it implemented in both add_depends and pagespec_match_list. The add_depends implementation is optimised to only try one page if the pagespec's influences are all static, and do not vary by page matched. --- doc/todo/dependency_types.mdwn | 51 ------------------------------------------ 1 file changed, 51 deletions(-) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index 6ca06fdab..e95965c33 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -564,57 +564,6 @@ SuccessReason(page, index) => right `HardFailReason() | SuccessReason(bugs/foo)` => `HardFailReason()` => right -#### High-level Calculation and Storage - -Naively calculating the full influence list for a pagespec requires trying -to match it against every page in the wiki. I'd like to avoid doing such -expensive matching redundantly. - -It may be possible, for some types of pagespecs, to just try matching a -single, arbitrary page against it, and know the full influence list has -been obtained. It seems to be that case that if a pagespec has any -influences, matching any page will return at least one. So if none are -returned, we can skip trying other pages. - -If the influence list does not include the page that was tried, we know -that the pagespec does not things like `link()` and `title()`, that are -influenced by the page's own content. So it *might* be safe to not try -matching any more pages in this case too. I think it would work for all -current pagespec terms. There might be a hypothetical term where this -optimisation doesn't work. We could add a special case to ensure it can -work: If a term declares it is unfluenced by "", then it means it is -always influenced by the matching page. - -Anyway, this seems worth doing: 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. - -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. - -If `pagespec_match_depends` can be used by all plugins, then great, -influences are automatically calculated, no extra work needs to be done. - -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. - -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. - -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. - -> I've implemented influence calculation in `add_depends`. As expected, -> it means rather a lot more work, and makes some things much slower. -> Optimisations next.. --[[Joey]] - #### Influence types Note that influences can also have types, same as dependency types. -- cgit v1.2.3 From a75591eaa772c1b875cca2d96b5015935a8617f3 Mon Sep 17 00:00:00 2001 From: "http://www.cse.unsw.edu.au/~willu/" Date: Fri, 9 Oct 2009 18:08:21 -0400 Subject: response --- doc/todo/dependency_types.mdwn | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'doc') diff --git a/doc/todo/dependency_types.mdwn b/doc/todo/dependency_types.mdwn index e95965c33..1c2f579b3 100644 --- a/doc/todo/dependency_types.mdwn +++ b/doc/todo/dependency_types.mdwn @@ -408,6 +408,11 @@ can indirectly influence what pages a pagespec matches. >>>> 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 matches. -- cgit v1.2.3 From 36003bad0ad5746af841a0373ded1e271ae57840 Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Fri, 9 Oct 2009 20:08:42 -0400 Subject: add news item for ikiwiki 3.20091009 --- doc/news/version_3.1415.mdwn | 7 ------- doc/news/version_3.20091009.mdwn | 14 ++++++++++++++ 2 files changed, 14 insertions(+), 7 deletions(-) delete mode 100644 doc/news/version_3.1415.mdwn create mode 100644 doc/news/version_3.20091009.mdwn (limited to 'doc') diff --git a/doc/news/version_3.1415.mdwn b/doc/news/version_3.1415.mdwn deleted file mode 100644 index 93310bc64..000000000 --- a/doc/news/version_3.1415.mdwn +++ /dev/null @@ -1,7 +0,0 @@ -ikiwiki 3.1415 released with [[!toggle text="these changes"]] -[[!toggleable text=""" - * img: Fix extra double quote with alt text. (smcv) - * Updated French debconf templates translation. Closes: #[535103](http://bugs.debian.org/535103) - * openid: Support Net::OpenID 2.x when pretty-printing - openids. (smcv) - * highlight: Fix utf-8 encoding bug. Closes: #[535028](http://bugs.debian.org/535028)"""]] \ No newline at end of file diff --git a/doc/news/version_3.20091009.mdwn b/doc/news/version_3.20091009.mdwn new file mode 100644 index 000000000..9ab1299b9 --- /dev/null +++ b/doc/news/version_3.20091009.mdwn @@ -0,0 +1,14 @@ +ikiwiki 3.20091009 released with [[!toggle text="these changes"]] +[[!toggleable text=""" + * parentlinks: Add has\_parentlinks template parameter to allow styling + the toplevel index differently etc. + * img: Correct bug in image size calculation code. + * img: Fix dependency code for full size images. + * toggle, relativedate: Support templates that add attributes + to the body tag. + * Support RPC::XML 0.69's incompatible object instantiation method. + * mirrorlist: Display nothing if list is empty. + * Fix a bug that could lead to duplicate links being recorded + for tags. + * Optimize away most expensive file prune calls, when refreshing, + by only checking new files."""]] \ No newline at end of file -- cgit v1.2.3