forward-chan (empty) → 0.0.0.0

raw patch · 5 files changed

+354/−0 lines, 5 filesdep +SafeSemaphoredep +basedep +stmsetup-changed

Dependencies added: SafeSemaphore, base, stm, unagi-chan

Files

Control/Concurrent/Chan/Forwardable.hs +106/−0
Control/Concurrent/Chan/Forwardable/Internals.hs +14/−0
LICENSE +201/−0
Setup.hs +2/−0
forward-chan.cabal +31/−0

+ Control/Concurrent/Chan/Forwardable.hs view

@@ -0,0 +1,106 @@+{- | A concurrent FIFO queue which behaves like Base's Chan with the new added 'forward' primative+ for merging two channels. Unlike duplicate style merging, when two channels are forwarded to each other,+ writes to one channel will not be duplicated to both channels, rather it will be as if both channels contents+ had been merged and all their outstanding and future references now point to this new channel.++ See <http://github.com/mmirman/forward-chan> for futher specification.+ -}+module Control.Concurrent.Chan.Forwardable ( Chan()+                                           , newChan+                                           , writeChan+                                           , readChan+                                           , forwardChan+                                           , getChanContents+                                           , writeList2Chan+                                           ) where++import Control.Concurrent.Chan.Forwardable.Internals++import qualified Control.Concurrent.Chan.Unagi as U+import Data.IORef+import Data.Typeable+import Control.Concurrent (forkIO)+import GHC.Base (join)+import System.IO.Unsafe ( unsafeInterleaveIO )++-- | Create a new channel+newChan :: IO (Chan a)+newChan = do+  (ci,co) <- U.newChan+  mi <- newIORef ci+  to <- newIORef co+  return $ Chan mi to++{- | Write a value to the channel.++If the channel becomes forwarded+at any time in the future, any thread+waiting on a value from the forwarded+channel may receive this value.+-}+writeChan (Chan mi _) v = do+  ci <- readIORef mi+  U.writeChan ci $ return v++{- | Read a value from a channel.+   +If a thread is waiting at a readChan+and another thread forwards this channel+to another (or visa versa) and the other+channel contains elements, this read might+now consume that element.+-}+readChan (Chan mi to) = join $ readIORef to >>= U.readChan++{- | Forward takes two channels and makes them act as one.+It obeys a few properties:+ +* /Commutivity/: @'forwardChan' a b === 'forwardChan' b a@++* /Behavioral Transitivity/: @('forwardChan' a b >> 'forwardChan' b c) === ('forwardChan' a b >> 'forwardChan' a c)@++* /Equal Opportunity/: A write to either channel before or after the forward will be able to be consumed by a read on either of the channels, and+there will be no unexpected starvation or race conditions.++* /Early Bird Gets The Worm/: The first thread to read from either channel will, after a 'forward', always recieve+the next available item.  Similarly, items written to either channel are read in the same order they were written in.++* /Note/: if @a '==' b@ is @False@, then after @'forwardChan' a b@ will not cause @a '==' b@ to become @True@.++-}+forwardChan :: Chan a -> Chan a -> IO ()    +forwardChan c@(Chan mi to) (Chan mi' to') = do+  ci' <- readIORef mi+  atomicWriteIORef mi' =<< readIORef mi+  +  co' <- readIORef to'+  atomicWriteIORef to' =<< readIORef to+    +  let readIfAvailable av non = do+        (v,_) <- U.tryReadChan co'+        v <- U.tryRead v+        case v of+          Just _ -> av =<< join (U.readChan co')+          _ -> non++      getOldOrNew = readIfAvailable return $ readChan c++      useAll :: IO ()+      useAll = readIfAvailable (\v -> writeChan c v >> useAll) $ return ()+        +  useAll+  U.writeChan ci' $ getOldOrNew -- executes if we're stuck on a read.+++++-- | Return a lazy list representing the contents of the supplied 'Chan'+getChanContents :: Chan a -> IO [a]+getChanContents ch = unsafeInterleaveIO $ do+  x  <- readChan ch+  xs <- getChanContents ch+  return $ x:xs++-- | Write an entire list of items to a 'Chan'.+writeList2Chan :: Chan a -> [a] -> IO ()+writeList2Chan ch ls = sequence_ (map (writeChan ch) ls)

+ Control/Concurrent/Chan/Forwardable/Internals.hs view

@@ -0,0 +1,14 @@+module Control.Concurrent.Chan.Forwardable.Internals where++import qualified Control.Concurrent.Chan.Unagi as U+import Data.IORef+import Data.Typeable++-- | A forwardable channel.+-- It supports all the standard channel operations+-- as layed out in the base library (as of 4.10.0.0)+-- except 'dupChan'+data Chan a = Chan { inChan :: IORef (U.InChan (IO a)), -- ^ a reference to an in-channel of actions that output the value. Warning: custom playing with these internals is likely to break forward's nice properties.+                     outChan :: IORef (U.OutChan (IO a)) -- ^ a reference to an out-channel of actions that output the value. +                   }+               deriving (Eq, Typeable)

+ LICENSE view

@@ -0,0 +1,201 @@+                                 Apache License+                           Version 2.0, January 2004+                        http://www.apache.org/licenses/++   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++   1. Definitions.++      "License" shall mean the terms and conditions for use, reproduction,+      and distribution as defined by Sections 1 through 9 of this document.++      "Licensor" shall mean the copyright owner or entity authorized by+      the copyright owner that is granting the License.++      "Legal Entity" shall mean the union of the acting entity and all+      other entities that control, are controlled by, or are under common+      control with that entity. For the purposes of this definition,+      "control" means (i) the power, direct or indirect, to cause the+      direction or management of such entity, whether by contract or+      otherwise, or (ii) ownership of fifty percent (50%) or more of the+      outstanding shares, or (iii) beneficial ownership of such entity.++      "You" (or "Your") shall mean an individual or Legal Entity+      exercising permissions granted by this License.++      "Source" form shall mean the preferred form for making modifications,+      including but not limited to software source code, documentation+      source, and configuration files.++      "Object" form shall mean any form resulting from mechanical+      transformation or translation of a Source form, including but+      not limited to compiled object code, generated documentation,+      and conversions to other media types.++      "Work" shall mean the work of authorship, whether in Source or+      Object form, made available under the License, as indicated by a+      copyright notice that is included in or attached to the work+      (an example is provided in the Appendix below).++      "Derivative Works" shall mean any work, whether in Source or Object+      form, that is based on (or derived from) the Work and for which the+      editorial revisions, annotations, elaborations, or other modifications+      represent, as a whole, an original work of authorship. For the purposes+      of this License, Derivative Works shall not include works that remain+      separable from, or merely link (or bind by name) to the interfaces of,+      the Work and Derivative Works thereof.++      "Contribution" shall mean any work of authorship, including+      the original version of the Work and any modifications or additions+      to that Work or Derivative Works thereof, that is intentionally+      submitted to Licensor for inclusion in the Work by the copyright owner+      or by an individual or Legal Entity authorized to submit on behalf of+      the copyright owner. For the purposes of this definition, "submitted"+      means any form of electronic, verbal, or written communication sent+      to the Licensor or its representatives, including but not limited to+      communication on electronic mailing lists, source code control systems,+      and issue tracking systems that are managed by, or on behalf of, the+      Licensor for the purpose of discussing and improving the Work, but+      excluding communication that is conspicuously marked or otherwise+      designated in writing by the copyright owner as "Not a Contribution."++      "Contributor" shall mean Licensor and any individual or Legal Entity+      on behalf of whom a Contribution has been received by Licensor and+      subsequently incorporated within the Work.++   2. Grant of Copyright License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      copyright license to reproduce, prepare Derivative Works of,+      publicly display, publicly perform, sublicense, and distribute the+      Work and such Derivative Works in Source or Object form.++   3. Grant of Patent License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      (except as stated in this section) patent license to make, have made,+      use, offer to sell, sell, import, and otherwise transfer the Work,+      where such license applies only to those patent claims licensable+      by such Contributor that are necessarily infringed by their+      Contribution(s) alone or by combination of their Contribution(s)+      with the Work to which such Contribution(s) was submitted. If You+      institute patent litigation against any entity (including a+      cross-claim or counterclaim in a lawsuit) alleging that the Work+      or a Contribution incorporated within the Work constitutes direct+      or contributory patent infringement, then any patent licenses+      granted to You under this License for that Work shall terminate+      as of the date such litigation is filed.++   4. Redistribution. You may reproduce and distribute copies of the+      Work or Derivative Works thereof in any medium, with or without+      modifications, and in Source or Object form, provided that You+      meet the following conditions:++      (a) You must give any other recipients of the Work or+          Derivative Works a copy of this License; and++      (b) You must cause any modified files to carry prominent notices+          stating that You changed the files; and++      (c) You must retain, in the Source form of any Derivative Works+          that You distribute, all copyright, patent, trademark, and+          attribution notices from the Source form of the Work,+          excluding those notices that do not pertain to any part of+          the Derivative Works; and++      (d) If the Work includes a "NOTICE" text file as part of its+          distribution, then any Derivative Works that You distribute must+          include a readable copy of the attribution notices contained+          within such NOTICE file, excluding those notices that do not+          pertain to any part of the Derivative Works, in at least one+          of the following places: within a NOTICE text file distributed+          as part of the Derivative Works; within the Source form or+          documentation, if provided along with the Derivative Works; or,+          within a display generated by the Derivative Works, if and+          wherever such third-party notices normally appear. The contents+          of the NOTICE file are for informational purposes only and+          do not modify the License. You may add Your own attribution+          notices within Derivative Works that You distribute, alongside+          or as an addendum to the NOTICE text from the Work, provided+          that such additional attribution notices cannot be construed+          as modifying the License.++      You may add Your own copyright statement to Your modifications and+      may provide additional or different license terms and conditions+      for use, reproduction, or distribution of Your modifications, or+      for any such Derivative Works as a whole, provided Your use,+      reproduction, and distribution of the Work otherwise complies with+      the conditions stated in this License.++   5. Submission of Contributions. Unless You explicitly state otherwise,+      any Contribution intentionally submitted for inclusion in the Work+      by You to the Licensor shall be under the terms and conditions of+      this License, without any additional terms or conditions.+      Notwithstanding the above, nothing herein shall supersede or modify+      the terms of any separate license agreement you may have executed+      with Licensor regarding such Contributions.++   6. Trademarks. This License does not grant permission to use the trade+      names, trademarks, service marks, or product names of the Licensor,+      except as required for reasonable and customary use in describing the+      origin of the Work and reproducing the content of the NOTICE file.++   7. Disclaimer of Warranty. Unless required by applicable law or+      agreed to in writing, Licensor provides the Work (and each+      Contributor provides its Contributions) on an "AS IS" BASIS,+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or+      implied, including, without limitation, any warranties or conditions+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A+      PARTICULAR PURPOSE. You are solely responsible for determining the+      appropriateness of using or redistributing the Work and assume any+      risks associated with Your exercise of permissions under this License.++   8. Limitation of Liability. In no event and under no legal theory,+      whether in tort (including negligence), contract, or otherwise,+      unless required by applicable law (such as deliberate and grossly+      negligent acts) or agreed to in writing, shall any Contributor be+      liable to You for damages, including any direct, indirect, special,+      incidental, or consequential damages of any character arising as a+      result of this License or out of the use or inability to use the+      Work (including but not limited to damages for loss of goodwill,+      work stoppage, computer failure or malfunction, or any and all+      other commercial damages or losses), even if such Contributor+      has been advised of the possibility of such damages.++   9. Accepting Warranty or Additional Liability. While redistributing+      the Work or Derivative Works thereof, You may choose to offer,+      and charge a fee for, acceptance of support, warranty, indemnity,+      or other liability obligations and/or rights consistent with this+      License. However, in accepting such obligations, You may act only+      on Your own behalf and on Your sole responsibility, not on behalf+      of any other Contributor, and only if You agree to indemnify,+      defend, and hold each Contributor harmless for any liability+      incurred by, or claims asserted against, such Contributor by reason+      of your accepting any such warranty or additional liability.++   END OF TERMS AND CONDITIONS++   APPENDIX: How to apply the Apache License to your work.++      To apply the Apache License to your work, attach the following+      boilerplate notice, with the fields enclosed by brackets "{}"+      replaced with your own identifying information. (Don't include+      the brackets!)  The text should be enclosed in the appropriate+      comment syntax for the file format. We also recommend that a+      file or class name and description of purpose be included on the+      same "printed page" as the copyright notice for easier+      identification within third-party archives.++   Copyright {yyyy} {name of copyright owner}++   Licensed under the Apache License, Version 2.0 (the "License");+   you may not use this file except in compliance with the License.+   You may obtain a copy of the License at++       http://www.apache.org/licenses/LICENSE-2.0++   Unless required by applicable law or agreed to in writing, software+   distributed under the License is distributed on an "AS IS" BASIS,+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+   See the License for the specific language governing permissions and+   limitations under the License.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ forward-chan.cabal view

@@ -0,0 +1,31 @@+name:                forward-chan+version:             0.0.0.0+synopsis:            Concurrent channels with a forwarding primitive+description:+  An implementation of the forward primitive, useful for proof terms from the sequent caluclus formulation of linear logic+  .+  See <http://github.com/mmirman/forward-chan> and <http://www.cs.cmu.edu/~fp/papers/tldi12.pdf> for more information on this primitive.++homepage:            http://github.com/mmirman/forward-chan+license:             Apache+license-file:        LICENSE+author:              Matthew Mirman+maintainer:          matt@mirman.com++category:            Concurrency+build-type:          Simple+cabal-version:       >=1.8++source-repository head+  type:    git+  location: git://github.com/mmirman/forward-chan.git++library+  exposed-modules:     Control.Concurrent.Chan.Forwardable+  exposed-modules:     Control.Concurrent.Chan.Forwardable.Internals+  build-depends:       base >= 4.7.0.0 && < 6.0,+                       unagi-chan < 1.0,+                       SafeSemaphore >= 0.7 && < 1.0,+                       stm++  hs-source-dirs:      .