[prev in list] [next in list] [prev in thread] [next in thread]
List: darcs-devel
Subject: [darcs-devel] darcs patch: Implement caching of git sequences in
From: Juliusz Chroboczek <Juliusz.Chroboczek () pps ! jussieu ! fr>
Date: 2005-10-31 13:23:52
Message-ID: E1EWZdg-0004iA-EC () lanthane ! pps ! jussieu ! fr
[Download RAW message or body]
Mon Oct 31 14:21:39 CET 2005 Juliusz Chroboczek <jch@pps.jussieu.fr>
* Implement caching of git sequences in GitRepo.
[Attachment #3 (text/x-darcs-patch)]
New patches:
[Implement caching of git sequences in GitRepo.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051031132139] {
hunk ./GitRepo.lhs 40
+-- String-indexed sequences
+type SSequence a = [(String, a)]
+
+-- A GitSequence is a SSequence of patches (almost, because David
+-- didn't make PatchInfos lazy).
+type GitSubsequence = [(PatchInfo, Maybe Patch)]
+type GitSequence = SSequence GitSubsequence
+
+-- The sequence caching monad.
+-- This is a state passing monad in which the state is monotonic and
+-- has a very particular shape.
+
+data SC a b = SC !([SSequence a] -> (b, [SSequence a]))
+type GSC a = SC [(PatchInfo, Maybe Patch)] a
+
+instance Monad (SC a) where
+ return x = SC (\s -> (x, s))
+ (SC a) >>= f = SC (\s -> let (a', s') = (a s)
+ (SC f') = f a'
+ in f' s')
+
+-- remember updates the state.
+remember :: (SSequence a) -> SC a (SSequence a)
+remember ss =
+ SC (\sseq -> (ss, (sseq ++ [ss])))
+
+-- recall reads the cached state. It uses find_sequence, which also
+-- checks for a proper tail of a cached sequence
+recall :: String -> (SC a (Maybe (SSequence a)))
+recall s = SC (\ss -> ((find_sequence s ss), ss))
+
+run :: SC a b -> b
+run (SC f) = fst (f [])
+
+
+--
+
hunk ./GitRepo.lhs 81
- map snd (really_read_repo repo h [])
+ map snd (run (really_read_repo repo h))
hunk ./GitRepo.lhs 83
-type GitSubsequence = [(PatchInfo, Maybe Patch)]
-type GitSequence = [(String, [(PatchInfo, Maybe Patch)])]
-
-really_read_repo :: String -> String -> GitSequence -> GitSequence
-really_read_repo _ sha1 seen | sha1 `insequence` seen =
- snd (split_sequence (Just sha1) seen)
-really_read_repo repo sha1 seen =
- let commit = readGitCommit repo sha1
- parents = gitCommitParents commit
- in case parents of
- [] -> [(sha1, [gitCommitToPIMP repo commit Nothing])]
- [p] ->
- let p' = readGitCommit repo p
- slurpy = slurpGitCommit repo p'
- in ((sha1, [gitCommitToPIMP repo commit (Just slurpy)]) :
- really_read_repo repo p seen)
- ps ->
- let histories = read_multiple_repos ps seen
- (ancestor, history) = merge_multiple_sequences histories
- a_commit = readGitCommit repo `liftM` ancestor
- a_slurpy = slurpGitCommit repo `liftM` a_commit
- slurpy = applySequenceToGitSlurpy ancestor history $
- (fromMaybe emptyGitSlurpy a_slurpy)
- in ((sha1, [gitCommitToPIMP repo commit (Just slurpy)]) :
- history)
+really_read_repo :: String -> String -> GSC GitSequence
+really_read_repo repo sha1 =
+ do found <- recall sha1
+ case found of
+ Just s -> return s
+ Nothing -> do
+ let commit = readGitCommit repo sha1
+ parents = gitCommitParents commit
+ case parents of
+ [] ->
+ remember [(sha1, [gitCommitToPIMP repo commit Nothing])]
+ [p] ->
+ do let p' = readGitCommit repo p
+ slurpy = slurpGitCommit repo p'
+ history <- really_read_repo repo p
+ remember $
+ ((sha1,
+ [gitCommitToPIMP repo commit (Just slurpy)]) :
+ history)
+ ps ->
+ do histories <- mapM (really_read_repo repo) ps
+ let (ancestor, history) =
+ merge_multiple_sequences histories
+ a_commit = readGitCommit repo `liftM` ancestor
+ a_slurpy = slurpGitCommit repo `liftM` a_commit
+ slurpy =
+ applySequenceToGitSlurpy ancestor history $
+ (fromMaybe emptyGitSlurpy a_slurpy)
+ remember $
+ ((sha1,
+ [gitCommitToPIMP repo commit (Just slurpy)]) :
+ history)
hunk ./GitRepo.lhs 118
- read_multiple_repos
- :: [String] -> GitSequence -> [GitSequence]
- read_multiple_repos [] _ = []
- read_multiple_repos (p:ps) seen' =
- let ph = really_read_repo repo p seen'
- in ph:(read_multiple_repos ps ph)
hunk ./GitRepo.lhs 129
-insequence :: String -> [(String, a)] -> Bool
+insequence :: String -> (SSequence a) -> Bool
hunk ./GitRepo.lhs 139
-split_sequence :: Maybe String -> [(String, [a])] -> ([a], [(String, [a])])
+split_sequence :: Maybe String -> (SSequence [a]) -> ([a], SSequence [a])
hunk ./GitRepo.lhs 147
-common_ancestor :: [(String, a)] -> [(String, b)] -> Maybe String
+find_sequence :: String -> [SSequence a] -> Maybe (SSequence a)
+find_sequence _ [] = Nothing
+find_sequence "" _ = Nothing
+find_sequence a (h:t) =
+ case find_sequence' a h of
+ Nothing -> find_sequence a t
+ Just s' -> Just s'
+ where find_sequence' _ [] = Nothing
+ find_sequence' a' s@((b,_):_) | a' == b = Just s
+ find_sequence' a' (_:bs) = find_sequence' a' bs
+
+common_ancestor :: (SSequence a) -> (SSequence b) -> Maybe String
}
Context:
[Remove obsolete comment.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051027183940]
[Use gitCommitDatePS instead of gitCommitDate when choosing Git ancestors.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051027182421]
[Use PackedStrings when parsing Git authors.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051027182400]
[Use the new breakFirstPairPS instead of break2PS.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051027180138]
[Change breakFirstPairPS to return slightly larger strings.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051027180107]
[Use packed strings when parsing Git commits.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051026005323]
[Implement break2PS.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051026005236]
[Clarify docs for building darcs-git.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051025231344]
[Choose better ancestors for Git merges.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051025215522
The common ancestor will be chosen optimally assuming that the Git
ancestry graph is a semilattice and commit dates are monotonic. If
the Git ancestry graph is unstructured, the youngest ancestor will
be chosen.
If Git dates are not ordered, all bets are off.
The algorithm is at least O(h*w^2), where h is the height of the
ancestry graph and w is the number of ancestors, but profiling shows
that this doesn't matter much -- commuting patches is what takes all
the time.
]
[Implement gitCommitDate.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051025213832]
[Merge changes
Ian Lynagh <igloo@earth.li>**20051008225210]
[specify default --author in whatsnew.pl.
David Roundy <droundy@darcs.net>**20051007235714]
[fix bug in whatsnew on files without trailing newlines.
David Roundy <droundy@darcs.net>**20051004124355]
[add test for whatsnew -s on file without newline.
David Roundy <droundy@darcs.net>**20050905123225]
[remove old footnote that caused doc-building trouble.
David Roundy <droundy@darcs.net>**20051008002612]
[use prefix and userchunkPS in coolContextHunk
Tommy Pettersson <ptp@lysator.liu.se>**20050923093032
This makes escaping of trailing spaces work in unified output.
]
[add changelog entry for bug #512.
David Roundy <droundy@darcs.net>**20051007123717]
[make --summary have effect in interactive commands
David Roundy <droundy@darcs.net>**20051007123507]
[make --dry-run --summary indent the summaries like changes does.
David Roundy <droundy@darcs.net>**20051007123427]
[avoid excess printing in set_scripts_executable.pl.
David Roundy <droundy@darcs.net>**20051007112545]
[fix documentation typos
Andres Loeh <loeh@iai.uni-bonn.de>**20050918175732]
[description environment for explanation of --summary flags
Andres Loeh <loeh@iai.uni-bonn.de>**20050918175612]
[remove/change/fix some quotation marks
Andres Loeh <loeh@iai.uni-bonn.de>**20050918171105]
[remove occurrences of \bf, \tt, and \em
Andres Loeh <loeh@iai.uni-bonn.de>**20050918170214]
[add executable bit support to Readable/WriteableDirectory.
David Roundy <droundy@darcs.net>**20051003123240]
[fix bug in set_scripts_executable test, and related bug in apply.
David Roundy <droundy@darcs.net>**20051006111849]
[clean up tests/set_scripts_executable.pl.
David Roundy <droundy@darcs.net>**20051004131951]
[make --set-scripts-executable work once again.
David Roundy <droundy@darcs.net>**20051004131756]
[remove occurances of "'" that messed up my emacs coloring...
David Roundy <droundy@darcs.net>**20050919122443]
[add two changelog entries.
David Roundy <droundy@darcs.net>**20051004132328]
[update copyright dates.
David Roundy <droundy@darcs.net>**20051004131936]
[only use ascii chars in quoted escapes of non-printable chars
Tommy Pettersson <ptp@lysator.liu.se>**20050920163959
Haskell interprets Char as unicode regardless of the systems locale,
so isPrint can't be used the way it was used to find suitable escape
quotings. Ascii fortunately is unicode, so the simple fix is to restrict
escape quotings to only use (printable) ascii chars.
]
[Installation doc readability fixes
Thomas Zander <zander@kde.org>**20050924163649]
[simplify docs-- why "CVS" is in the boring file is self-evident.
Mark Stosberg <mark@summersault.com>**20050927131847]
[add two new changelog entries.
David Roundy <droundy@darcs.net>**20050910110115]
[fix bug in resolve.pl test.
David Roundy <droundy@darcs.net>**20050910103833]
[give better output on sftp errors.
David Roundy <droundy@darcs.net>**20050908125423]
[make darcs not generate null binary patches when diffing.
David Roundy <droundy@darcs.net>**20050907125129]
[make darcs able to eliminate null binary and hunk patches when coalescing.
David Roundy <droundy@darcs.net>**20050907125104]
[add test that adding and removing binary files leaves no change.
David Roundy <droundy@darcs.net>**20050907122509]
[fix some typos in comments
Conrad Parker <conrad@metadecks.org>**20050904225715]
[Make print_dry_run_message_and_exit print summaries if All and Summary.
David Roundy <droundy@darcs.net>**20050904125434
This is a somewhat hokey way to make --all --summary print summary
messages.
]
[add changelog entry for configure script checking on darcs being present.
David Roundy <droundy@darcs.net>**20050905113258]
[fix bug where we tried to run darcs when darcs wasn't present.
David Roundy <droundy@darcs.net>**20050905112935]
[revert accidental directory name change in Test.
David Roundy <droundy@darcs.net>**20050904123424]
[add changelog entry for recent pristine bugfix.
David Roundy <droundy@darcs.net>**20050903134039]
[Fix typos in description of unpull.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20051006204813
Thanks to frithjof.
]
[-add test script for --set-scripts-executable
Mark Stosberg <mark@summersault.com>**20050901015046
It's currently failing because darcs is currently broken in this regard. I commented
out a "TODO" test in case you want to make to this a TODO test until
someone gets to it.
]
[clean up docs on flags directly to darcs (not to a darcs command).
David Roundy <droundy@darcs.net>**20050903124050]
[bump version to 1.0.4rc1.
David Roundy <droundy@darcs.net>**20050903114002]
[update the web page to direct new users first to the precompiled binaries rather \
than first to the source zooko@zooko.com**20050902162737]
[add test script that displays --no-pristine test-related bug.
David Roundy <droundy@darcs.net>**20050903132906]
[fix bug triggered by --no-pristine-tree and running test.
David Roundy <droundy@darcs.net>**20050903132055
The trouble was that the NoPristine version of createPristineDirectoryTree
would fail if the directory already exists, which isn't the intended
behavior. I also took this opportunity to remove the "stubbornly" function
and replace some stubborn directory creation with
createDirectoryIfMissing.
]
[don't create test directory if we don't want to actually run test.
David Roundy <droundy@darcs.net>**20050903130722]
[Change an rm_rf to a cleanup in tests/disable.pl
Ian Lynagh <igloo@earth.li>**20050902024711]
[TAG 1.0.4pre4
David Roundy <droundy@darcs.net>**20050901110418]
[add changelog entry for makefile fix.
David Roundy <droundy@darcs.net>**20050901110353]
[bump version to 1.0.4pre4.
David Roundy <droundy@darcs.net>**20050901110210]
[fix DESTDIR syntax errors in makefile
Andres Loeh <loeh@iai.uni-bonn.de>**20050831192410]
[fix "No root path(s) specified at ..." testsuite problem.
David Roundy <droundy@darcs.net>**20050830121603]
[add test that triggers "too many open files" bug.
David Roundy <droundy@darcs.net>**20050827192215
We just need to pull over 1024 patches at once to trigger this bug on my
linux system.
]
[TAG 1.0.4pre3
David Roundy <droundy@darcs.net>**20050831115448]
[add two changelog entries.
David Roundy <droundy@darcs.net>**20050831113335]
[only create directories on install if they don't exist (bug #494)
David Roundy <droundy@darcs.net>**20050831113142]
[fix bug in whatsnew -l -l (rt#501).
David Roundy <droundy@darcs.net>**20050831110552]
[fix typo in docs.
David Roundy <droundy@darcs.net>**20050831002520]
[fix --posthook code to pass tests.
David Roundy <droundy@darcs.net>**20050830132225]
[add test for --disable.
David Roundy <droundy@darcs.net>**20050830132122]
[add changelog entry for --posthook.
David Roundy <droundy@darcs.net>**20050830132110]
[add skeleton posthook test.
David Roundy <droundy@darcs.net>**20050827123744]
[posthook documentation
Jason Dagit <dagit@codersbase.com>**20050825045706]
[changed from --posthook-command to posthook
Jason Dagit <dagit@codersbase.com>**20050825043414]
[now the posthook options appear for each command
Jason Dagit <dagit@codersbase.com>**20050825043305]
[posthook for apply
Jason Dagit <dagit@codersbase.com>**20050803070343
With this patch it is now possible to specify a command to run after every
successful apply.
]
[added run_posthook for actually running posthooks
Jason Dagit <dagit@codersbase.com>**20050803070156
This adds the function run_posthook which should be used to run posthooks.
The code was added to Test.lhs, but there may be a better place for this code.
]
[added posthook command line switches
Jason Dagit <dagit@codersbase.com>**20050803065956
Added generic posthook command line switches. This patch does not add any
posthooks to any command.
]
[Rewrite gcau, add explanatory comment from David and some TODO notes
Ian Lynagh <igloo@earth.li>**20050830020943]
[update building darcs section of manual.
David Roundy <droundy@darcs.net>**20050829120152]
[add bench directory with a single script in it.
David Roundy <droundy@darcs.net>**20050828114118
See bench/README for discussion of the idea behind this.
]
[New implementation of comparePS, based on memcmp. 1/5 space usage, 96% faster
dons@cse.unsw.edu.au**20050827070030]
[Use substrPS-less versions of initPS and tailPS
dons@cse.unsw.edu.au**20050827023214]
[remove hideous malloc hack.
David Roundy <droundy@darcs.net>**20050818161411]
[change my AUTHORS email to droundy@darcs.net.
David Roundy <droundy@abridgegame.org>**20050808124703]
[fix mkstemp implementation for win32
Peter Strand <peter@zarquon.se>**20050810211303]
[Implement parts of System.Posix.(IO|Files) for win32
peter@zarquon.se**20050809200433]
[implement RawMode with library functions instead of ffi
peter@zarquon.se**20050809200148]
[call hsc2hs without output filename argument
peter@zarquon.se**20050808220444]
[Rename compat.c to c_compat.c to avoid object filename conflict with Compat.hs
peter@zarquon.se**20050731114011]
[Move atomic_create/sloppy_atomic_create to Compat
Ian Lynagh <igloo@earth.li>**20050730141703]
[Split the raw mode stuff out into its own .hsc file. Windows needs some TLC
Ian Lynagh <igloo@earth.li>**20050730134030]
[Move maybe_relink out of compat.c
Ian Lynagh <igloo@earth.li>**20050730131205]
[Remove is_symlink
Ian Lynagh <igloo@earth.li>**20050730122255]
[Move mkstemp to Compat.hs
Ian Lynagh <igloo@earth.li>**20050730020918]
[Remove unused function
Ian Lynagh <igloo@earth.li>**20050730010118]
[Start Compat.hs, and move stdout_is_a_pipe from compat.c
Ian Lynagh <igloo@earth.li>**20050730004829]
[fix for bug Ian found in apply.
David Roundy <droundy@abridgegame.org>**20050811162558
This is the bug manifested in the cabal repository.
]
[fix compilation errors with ghc-6.2.2 on win32
Peter Strand <peter@zarquon.se>**20050809192759]
[Retain both Git's author and committer.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20050810000820]
[Move slurping into syncPristine.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20050809232101
Avoids creating a useless pristine tree when there is none. Thanks to
Ian for pointing this out.
]
[Split --relink into --relink and --relink-pristine.
Juliusz Chroboczek <jch@pps.jussieu.fr>**20050809230951
Relinking the pristine tree breaks handling of timestamps, which causes
Darcs to compare file contents. It should not be used unless you know
what you are doing.
]
[make repair work on partial repositories.
David Roundy <droundy@abridgegame.org>**20050805113001]
[Cleanup --verbose handling in repair command
Matt Lavin <matt.lavin@gmail.com>**20050805020630]
[clean up Printer.wrap_text.
David Roundy <droundy@abridgegame.org>**20050808114844]
[add several changelog entries.
David Roundy <droundy@abridgegame.org>**20050808114800]
[improve EOD message a tad.
David Roundy <droundy@abridgegame.org>**20050807112644
This change also introduces a "wrapped_text" function in Printer, so we
won't have to worry so often about manually wrapping lines.
]
[changed ***DARCS*** to ***END OF DESCRIPTION***
Jason Dagit <dagit@codersbase.com>**20050729032543]
[remove unused opts argument from apply_patches and apply_patches_with_feedback
Matt Lavin <matt.lavin@gmail.com>**20050807031038]
[Use apply_patch_with_feedback from check and repair commands
Matt Lavin <matt.lavin@gmail.com>**20050805020830]
[add code to read patch bundles with added CRs.
David Roundy <droundy@abridgegame.org>**20050806222631
I think this'll address bug #291.
]
[accept command-line flags in any order.
David Roundy <droundy@abridgegame.org>**20050806211828
In particular, we no longer require that --flags precede filename and
repository arguments.
]
[show patch numbers instead of dots on get
Matt Lavin <matt.lavin@gmail.com>**20050804013649]
[add obliterate command as alias for unpull.
David Roundy <droundy@abridgegame.org>**20050804104929]
[Do not ask confirmation for revert -a
jani@iv.ro**20050627124011
Giving -a as a parameter means the user expects all changes to be reverted.
Just like for unrevert and record go ahead with it do not ask for confirmation.
]
[clarify help text for 'd' in SelectPatches.
David Roundy <droundy@abridgegame.org>**20050806231117]
[Add --with-static-libs configure flag for linking static versions of libraries.
v.haisman@sh.cvut.cz**20050729015539]
[add changelog entry for bug #477.
David Roundy <droundy@abridgegame.org>**20050806212148]
[changelog entry for bug #189.
David Roundy <droundy@abridgegame.org>**20050731132624]
[add description of how to add changelog entries to ChangeLog.README.
David Roundy <droundy@abridgegame.org>**20050806225901]
[Explain the missing ChangeLog
Mark Stosberg <mark@summersault.com>**20050526135421
It should be easy for casual users and contributors to view and update the
ChangeLog.
Providing a README file in the place where people are most likely to look
provides a very useful clue.
However, it's still not clear to me exactly how the system works, so I have
left a stub to complete that documentation.
Mark
]
[fix obsolete error explanation in get_extra bug.
David Roundy <droundy@abridgegame.org>**20050804130610]
[simplify fix for bug 463; reuse /// from FilePathUtils
Matt Lavin <matt.lavin@gmail.com>**20050804021130]
[Make curl exit with error on failed downloads
peter@zarquon.se**20050802192833]
[Bump up AC_PREREQ version to 2.59.
v.haisman@sh.cvut.cz**20050801173925]
[fix for bug 463 (with new test)
Matt Lavin <matt.lavin@gmail.com>**20050802002116]
[bump version number, since I just made a release.
David Roundy <droundy@abridgegame.org>**20050731190756]
[Use simpler curl_version() function to get version string.
Kannan Goundan <kannan@cakoose.com>**20050322221027]
[fix documentation on --reorder-patches.
David Roundy <droundy@abridgegame.org>**20050731185406]
[add changelog entry for bug #224.
David Roundy <droundy@abridgegame.org>**20050731133942]
[fix bug when editing long comment leaves empty file.
David Roundy <droundy@abridgegame.org>**20050731133612]
[TAG 1.0.4pre2
David Roundy <droundy@abridgegame.org>**20050731121029]
Patch bundle hash:
48799b1a2e71cc5a303fbb9d7b8f544aa701c2ae
_______________________________________________
darcs-devel mailing list
darcs-devel@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-devel
.
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic